本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

一連五天，我們介紹了Decrease and Conquer，今天和明天我們要介紹另一個主題 -- Divide and Conquer和兩種屬於這個類別的演算法，分別是Merge Sort（今天）和Quick Sort（明天），那就讓我們開始今天的主題吧。

Divide and Conquer的運作方式

Decrease and Conquer和Divide and Conquer都是將大問題拆解成小問題解決的運作方式，然而前者是將小問題的解決方式衍生到大問題去解決，但後者則是將解決小問題而有的小結果合併起來，變成大問題的解答，所以兩者還是有其區別。從上示意圖可知，原先有一問題（紅色），其大小為n，將其拆解成兩個子問題（藍色），大小分別為n/2，再進一步拆解成四個小子問題（大小分別為n/4）（黃色），此時，再針對這四個小子問題去解決，進而取得小子問題的解答（結果）（綠色），再將四個小子結果合併成兩個子結果（粉色），最後將兩個子結果合併成最終的結果（黑色）；這個就是Divide and Conquer的運作流程。

Merge Sort的流程

Merge Sort其實就是標準的Divide and Conquer，完全按照上面的圖進行拆解和組合，我們來看看GIF了解實際上Merge Sort是如何進行的吧：

從上GIF圖可以看到，在進行Divide的時候，會拆解成最小單位，然後在每一步Conquer的過程中進行Sort的動作，如此一來在進入下一階段的Conquer前，就會是兩個已經排列過的陣列合併。

Merge Sort的時間複雜度

Merge Sort保留了Binary Search的『砍半』手法，所以只要有砍半的動作，時間複雜度就會是Ｏ(㏒2 n)；但是，Merge Sort在進行Merge的時候，最壞的情況(Worst Case)是每一步的Conquer都要去做兩個陣列完整的比較後才能完成排序與合併，而這個動作的時間複雜度為Ｏ(n)；因此，整體來說，Merge Sort的時間複雜度需要合併這兩個結果，即為Ｏ(n·㏒2 n)。

小結

1. Divide and Conquer是將大問題拆解成小問題解決後，再將所有小問題的結果合併成大問題的結果。
2. Merge Sort的時間複雜度為Ｏ(n·㏒2 n)。

預告

明天我們將會介紹另一個Divide and Conquer的演算法-Quick Sort。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin