合併排序(Merge Sort)演算法是非常通用的排序演算法,是穩定排序,即便在最差的情況下也還有O(nlogn)的時間複雜度。



合併排序法(Merge Sort)

合併排序法的概念

合併排序法是最典型的分治(Divide and Conquer)演算法,將一整個序列分割成一個個元素,再兩兩一組依照元素大小填入至新的空間中來合併成新的,並且已經排序好的序列。

合併排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

首先將陣列對半切成:

索引    0   1   2   3   4   |   5   6   7   8   9
數值   69  81  30  38   9   |   2  47  61  32  79

再對半切成:

索引    0   1   |   2   3   4   ||   5   6   |   7   8   9
數值   69  81   |  30  38   9   ||   2  47   |  61  32  79

再對半切成:

索引    0   |   1   ||   2   |   3   4   |||   5   |   6   ||   7   |   8   9
數值   69   |  81   ||  30   |  38   9   |||   2   |  47   ||  61   |  32  79

再對半切成:

索引    0   ||   1   |||   2   ||   3   |   4   ||||   5   ||   6   |||   7   ||   8   |   9
數值   69   ||  81   |||  30   ||  38   |   9   ||||   2   ||  47   |||  61   ||  32   |  79

已經不能再切了,即可開始合併,一邊合併一邊把元素照順序排好:

索引    0    |   1    ||   2    |   3       4    |||   5   |    6    ||   7    |   8       9
數值   69    |  81    ||  30    |   9      38    |||   2   |   47    ||  61    |  32      79
                                   →───←                                     →───←

繼續合併:

索引    0        1     |   2        3       4     ||   5       6     |   7        8       9
數值   69       81     |   9       30      38     ||   2      47     |  32       61      79
       →────←       →────────←        →───←        →────────←

繼續合併:

索引    0        1         2        3       4      |   5       6         7        8       9
數值    9       30        38       69      81      |   2      32        47       61      79
       →─────────────────←         →─────────────────←

繼續合併:

索引    0        1         2        3       4          5       6         7        8       9
數值    2        9        30       32      38         47      61        69       79      81
       →────────────────────────────────────────←

合併完成,也排序完成了!

merge-sort

以上過程看起來十分直覺。程式實作時需要使用額外的空間來進行一邊合併一邊排序的動作。

合併排序法的程式實作

在實作程式的時候,應該要避免使用遞迴(Recursive)的結構,因為遞迴需要不斷地重新建構函數的堆疊空間,硬體資源的負擔會比較大,且若是遞迴層數過多還會導致堆疊溢出(Stack Overflow)。所以比較好的做法還是在一個函數內以迴圈迭代的方式來完成。

為了化簡遞迴轉迭代結構時的問題,在這裡不採取從中間開始分割的方式,而是直接跳過分割的動作,從合併開始進行。在觀察合併排序法的分割過程後,其實不難發現完整的子陣列的長度,合併過後的長度都會再乘上2,且即便是未達2的乘冪長度的陣列,也能進行合併的動作。也就是說,分割的動作其實並非必要,可以直接從前端開始直接合併2的乘冪個元素,先從1(20)個元素兩兩開始合併,再從2(21)個元素兩兩開始合併,再從4(22)個元素兩兩開始合併,再從8(23)個元素兩兩開始合併,依此類推。因此可以寫出如下的迭代版合併排序法:

實務上使用合併排序法時,常會去檢查子序列的大小是否過長(長度大於7~15),如果子序列長度不長,會使用適合拿來排序少量資料的插入排序等演算法來完成排序。

合併排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目備註
最差時間複雜度#{{O(n \log n)}}#
最佳時間複雜度#{{O(n \log n)}}#
平均時間複雜度#{{O(n \log n)}}#
額外最差空間複雜度#{{O(n)}}#
是否穩定