在之前的文章中, 我們講述了分而治之演算法, 而它的思想可以被用於排序中. 這種排序法設計的整體思路為 : 令 n 是當前要排序的元素數量, 若 n = 1, 則演算法終結; 當 n = 1 時, 電腦可以在瞬間通過交換來完成排序; 當 n > 1 時, 將序列劃分為 k 個子序列 (k \geq 2), 對每一個子序列進行排序, 再將有序的子序列合併為一個有序的序列

假設將 n 個元素的序列僅僅劃分為兩個序列, 稱這種劃分為二路劃分. 一種方式是將前 n - 1 個元素放入第一個子序列中 (不妨記為序列 A), 最後一個元素放入第二個序列 (不妨記為序列 B) 中. 按照這種方式對 A 遞迴地進行排序, 由於序列 B 中有且唯有一個元素, 因此序列 B 已經有序. 在序列 A 排序之後, 將兩個序列進行合併, 可以考慮使用插入排序法進行合併. 實際上, 這就是插入排序法的遞迴形式, 其時間複雜度為 O(n^{2})

另一種二路劃分是將最大的元素放入 B 中, 剩餘元素放入 A 中, 再對 A 遞迴地進行排序, 為了將排序之後的子序列 A 和 B 合併, 只需要將 B 附加在 A 的尾部即可. 如果使用交換的方法將更大的元素交換到 B 中, 則這實際上是選擇排序法的遞迴形式, 其時間複雜度為 O(n^{2}). 如果使用泡沫排序法將最大的元素逐漸交換到最右側的位置, 則這實際上是泡沫排序法的遞迴形式, 其時間複雜度為 O(n^{2})

上面這幾種方式對序列的劃分都是極其不平衡的. 不妨考慮稍微平衡一些的劃分 : 序列 A 中包含 \left \lfloor \frac {n}{2} \right \rfloor, 序列 B 中包含 n - \left \lfloor \frac {n}{2} \right \rfloor. 這時, 對序列 A 中的元素進行排序, 對序列 B 中的元素也作排序. 完成之後, 合併序列 A 與 B 得到一個有序的序列即可. 利用分而治之演算法的思想, 對子序列 A 和 B 同樣可以再次劃分

現只考慮對序列按照某個值 (不妨設為 M) 進行劃分, 當序列元素個數 nM 要大, 則將 \left \lfloor \frac {n}{M} \right \rfloor 個元素放入序列 A, 其餘元素放入序列 B. 若序列 A 和 B 的元素仍大於 M, 則繼續進行劃分, 直到子序列中的元素數量小於 M. 當得到一個元素個數小於 M 的子序列時, 便對子序列進行某種排序演算法. 設 E 為元素集合, M 為元素數量的上限, E = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}, 則可以寫出以下虛擬碼 :

void\ merge\_sort(E)\ \{\\ \ \ \ \ if(cardE \geq M)\ \{\\ \ \ \ \ \ \ \ \ i = \left \lfloor \frac {cardE}{M} \right \rfloor;\\ \ \ \ \ \ \ \ \ j = n - \left \lfloor \frac {cardE}{M} \right \rfloor;\\ \ \ \ \ \ \ \ \ A = \left \{ e_{1}, e_{2}, ..., e_{i} \right \rfloor;\\ \ \ \ \ \ \ \ \ B = \left \{ e_{i + 1}, e_{i + 2}, ..., e_{n} \right \rfloor;\\ \ \ \ \ \ \ \ \ merge\_sort(A);\\ \ \ \ \ \ \ \ \ merge\_sort(B);\\ \ \ \ \ \ \ \ \ merge(E, A, i, B, j);\ \ \ \ \ \ \ \ //合併\ A\ 與\ B\ 的元素歸入到\ E\ 中\\ \ \ \ \ \}else\ \{ \\ \ \ \ \ \ \ \ \ sort(E); \\ \ \ \ \ \} \\ \}

由於合併排序法使用分而治之演算法的思想, 因此我們可以根據分而治之演算法的時間複雜度分析, 對建立上述虛擬碼在最壞情況下的時間複雜度遞迴方程式 T(n). 首先, T(n) 滿足

T(n) = \begin {cases} \Theta(1) &{n < c} \\ aT(\frac {n}{b}) + D(n) + C(n) & {n \geq c} \end {cases}

n = 1 時, 序列已經有序了, 無須對其進行排序, 因此 c = 1. 當 n > 1 時, 我們對序列進行分解. 一般來說, 我們從中間一分為二, 此時得到的其中一個子序列的數量不一定為偶數. 現假定問題滿足 \log_{2}{n} 為一個整數, 稍後討論得到另外一個序列不是偶數個元素的情況. 另外, 之後我們也將證明從中間一分為二確實能夠使得 T(n) 取得最小值. 一分為二之後, 兩個子問題的規模為 \frac {n}{2}, 求解子問題所用時間為 2T(\frac {n}{2}). 一分為二實際上僅僅需要常數級別的時間. 因此, D(n) = \Theta(1). 合併 n 個元素需要 \Theta(n) 的時間, 因此 C(n) = \Theta(n). 不妨設

\Theta(1) = c_{0}, \Theta(n) = c_{1}n + c_{2}

其中, c_{0}, c_{1}, c_{2} 均為常數. 則

\Theta(1) + \Theta(n) = c_{1}n + c_{0} + c_{2} = \Theta(n)

於是, 最壞情況下的運作時間 T(n) 的遞迴方程式為

T(n) = \begin {cases} \Theta(1) & {n = 1} \\ 2T(\frac {n}{2}) + \Theta(n) & {n > 1} \end {cases}

還有兩個疑問點沒有解決 :

  • 我們需要分析問題不滿足 \log_{2}{n} 為整數時的情形
  • 我們還需要證明對於任意的 c > 0, 若且唯若 c = 1 時才能使 T(n) 取得最小值

若 \log_{2}{n} 不是一個整數, 那麼放入集合 A 中的元素有 \left \lfloor \frac {n}{2} \right \rfloor 個, 放入集合 B 中的元素為 n -  \left \lfloor \frac {n}{2} \right \rfloor 個. 此時, 我們得到了新的 T(n) 的遞迴方程式 :

T(n) = \begin {cases} \Theta(1) & {n = 1} \\ T(\left \lfloor \frac {n}{2} \right \rfloor) + T(n - \left \lfloor \frac {n}{2} \right \rfloor) + \Theta(n) & {n > 1} \end {cases}

不失一般性, 我們改寫 T(n)

T(n) = \begin {cases} \Theta(1) &{n < 2} \\ T(\left \lfloor \frac {n}{2} \right \rfloor) + T(n - \left \lfloor \frac {n}{2} \right \rfloor) + \Theta(n) &{n \geq 2} \end {cases}

現在, 我們需要證明對於任意 c > 1, 若且唯若 c = 2 時, 可以使得 T(n) 取得最小值. c 標誌著一個序列的元素上限, 若元素數量超過上限, 它將被分而治之. 因此, 我們考慮建立一個帶有參數 c 的一元函數 :

T(n) = \begin {cases} \Theta(1) &{n < 2} \\ T(\left \lfloor \frac {n}{c} \right \rfloor) + T(n - \left \lfloor \frac {n}{c} \right \rfloor) + \Theta(n) &{n \geq 2} \end {cases}

從遞迴方程式, 我們可以知道, 運算式 T(\left \lfloor \frac {n}{c} \right \rfloor) + T(n - \left \lfloor \frac {n}{c} \right \rfloor) 決定著 T(n) 的大小. 因此, 如果 T(\left \lfloor \frac {n}{c} \right \rfloor) + T(n - \left \lfloor \frac {n}{c} \right \rfloor) 可以取得最小值, 自然地, T(n) 取得最小值

引理 : 令 f(x) 滿足 f(y + d) - f(y) \geq f(z + d) - f(z), 其中 y \geq z, d > 0. 對於任意實數 r, 若且唯若 c = 2 時, f(\frac {r}{c}) + f(r - \frac {r}{c}) 取得最小值

:

z = y - d, 替換可得

f(y + d) - f(y) \geq f(y) - f(y - d)

移項得 f(y + d) + f(y - d) \geq 2f(y), 即 2f(y) \leq f(y + d) + f(y - d)

c \geq 2 時, 將 d = \frac {r}{2} - \frac {r}{c} y = \frac {r}{2} 代入, 得

2f(\frac {r}{2}) \leq f(\frac {r}{2} + \frac {r}{2} \ \frac {r}{c}) + f(\frac {r}{2} - \frac {r}{2} + \frac {r}{c}) \Rightarrow 2f(\frac {r}{2}) \leq f(r - \frac {r}{c}) + f(\frac {r}{c})

c < 2 時, 將 d = \frac {r}{c} - \frac {r}{2}y = \frac {y}{2} 代入, 得

2f(\frac {r}{2}) \leq f(\frac {r}{2} + \frac {r}{c} - \frac {r}{2}) + f(\frac {r}{2} - \frac {r}{c} + \frac {r}{2}) \Rightarrow 2f(\frac {r}{2}) \leq f(\frac {r}{c}) + f(r - \frac {r}{c})

於是有 2f(\frac {r}{2}) \leq f(r - \frac {r}{c}) + f(\frac {r}{c}). 換言之, f(r - \frac {r}{2}) + f(\frac {r}{2}) \leq f(r - \frac {r}{c}) + f(\frac {r}{c})

綜上所述, 若且唯若 c = 2 時, f(\frac {r}{c}) + f(r - \frac {r}{c}) 取得最小值

\blacksquare

上述引理對於任意實數 r 都成立, 那麼對於正整數 n 自然成立. 因此, 將一個序列從中間一分為二, 讓兩個子序列的數量近似相等.將序列從中間一分而為, 子序列的數量之多相差一個, 此時使用分而治之思想的合併排序法具有最佳性能. 此時, 可以直接去除虛擬碼中的 else 分支

T(n) 的遞迴方程式中, 取 c = 2, 得

T(n) = \begin {cases} 0 & {n = 0} \\ \Theta(1) & {n = 1} \\ T(\left \lfloor \frac {n}{2} \right \rfloor) + T(n - \left \lfloor \frac {n}{2} \right \rfloor) + \Theta(n) & {n > 1} \end {cases}

如果規定 \log_{2}{n} 為整數, 則 T(n) 會簡單一些 :

T(n) = \begin {cases} 0 & {n = 0} \\ \Theta(1) & {n = 1} \\2 T(\frac {n}{2}) + \Theta(n) & {n > 1} \end {cases}

上述遞迴方程式是可解的, 我們暫時還沒有講述如果解一個遞迴方程式, 在近期的文章中, 我會講述如何解一個遞迴方程式. 通過計算上述遞迴方程式 T(n), 可知合併排序法的時間複雜度為 \Theta(n \log {n}), 即 T(n) = \Theta(n \log {n})

合併排序法在最好和最壞的情況下, 其時間複雜度都為 \Theta(n \log {n}), 因此平均複雜度也為 \Theta(n \log {n})

精確地說, 當 c = 2 時的合併排序法為二路合併排序法. 接下來, 我將用圖像演示二路合併排序如何進行. 首先給定一些元素 :

按照之前我們給定的方法, 首先對序列進行劃分, 由於序列有九個元素, 因此左側序列中有四個元素, 右側序列中有五個元素 :

接著我們繼續劃分 :

對於左側的兩個子序列, 已經可以在常數時間內完成排序了, 所以我們進行交換 :

完成之後, 我們需要對左側的兩個子序列進行合併. 要進行合併, 一般的方法是選擇最小的元素放在第一個, 次小的元素放在第二個, 直到左側序列有序 :

接著對右側使用相同的方法進行劃分 :

右側的第一個子序列已經可以在常數時間內完成排序, 因此我們進行交換. 交換之後對第二個子序列進行劃分 :

接著, 對剩下的序列進行排序, 由於最後一個序列有且唯有一個元素, 它已經有序, 所以無須對其進行排序 :

現在我們發現最後兩個子序列已經有序了, 因此現在只需要合併右側這個序列即可 :

最後, 我們合併左側右側兩個子序列, 合併排序就完成了 :

在實際應用中, 一種簡單的方法就是使用連結串列存儲元素, 在鏈結串列的第 \left \lfloor \frac {n}{2} \right \rfloor 個結點處斷開成兩個大小相對一致的子鏈結串列. 合併的過程即是將兩個子鏈結串列合併到一起. C++ 標準樣板程式庫中, 針對 std::forward_liststd::list 的排序方法進行了特製化, 用的即是使用了分而治之演算法思想的二路合併排序法
上述討論的合併排序法也成為直接合併排序法, 遞迴形式的直接合併排序可以被改為非遞迴的形式. 還有另一種合併排序法稱為自然合併排序法. 在自然合併排序法中, 首先認定在輸入序列中已經存在有序子序列段, 認定的方法就是從左至右進行尋訪, 若第 i 個元素比第 i + 1 個元素大, 則 i 是一個分割點. 接下來, 合併被分割的有序段直到只剩下一個有序集合. 在最後的情況下, 自然合併排序法的時間複雜度為 O(n), 因為此時輸入序列已經有序, 但是直接合併排序法仍然需要 \left \lceil \log_{2}{n} \right \rceil 次合併. 在最壞的情況下, 輸入的序列是逆有序的, 每一個元素都是一個分割點, 此時自然合併排序法的性能不如直接合併排序法

在一般情況下, n 個元素序列有 \frac {n}{2} 個有序段, 因為第 i 個元素比第i + 1 個元素大的概率為 \frac {1}{2}. 如果開始的有序段僅有 \frac {n}{2} 個, 那麼自然合併排序法所需的合併比直接合併排序法要少. 但是自然合併排序法在認定初始有序段和記錄有序段邊界時需要額外的時間. 因此, 只有輸入序列確實有很少的有序段時, 才使用自然合併排序法

現在還有一個關於合併的問題. 一般來說, 我們通過配置一片能夠容納 n 個元素的記憶體, 然後尋訪各個子序列將元素放入到新配置的記憶體中, 這樣的合併排序的空間複雜度為 O(n). 我們希望有一種方法可以進行原地重排, 即空間複雜度為 O(1)

大家最容易想到的就是使用插入排序法進行合併, 但是插入排序法是針對單個元素的, 所以時間複雜度稍高. 我們這裡介紹一種旋轉的方法, 但是不針對這個演算法進行任何優化, 暫時僅將最簡單的旋轉演算法呈現給大家. 對於一個序列 \mathscr {E} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}, 以第一個元素為基準向左旋轉 k (0 \leq k \leq n) 個元素, 那麼序列會變為 \mathscr {E}' = \left \{ e_{k + 1}, e_{k + 2}, ..., e_{n}, e_{1}, e_{2}, ..., e_{k} \right \}; 以第一個元素為基準向右旋轉 k 個元素, 那麼序列會變為 \mathscr {E}'' = \left \{ e_{n - k + 1}, e_{n - k + 2}, ..., e_{n}, e_{1}, e_{2}, ..., e_{n - k} \right \}. 簡單地來說, 實際上旋轉序列就是對序列進行循環移位

運用旋轉這個思想, 我們可以讓合併更有效率. 對於一個給定的兩個有序子序列 \mathscr {E} = \left \{ x_{1}, x_{2}, ..., x_{n}, y_{1}, y_{2}, ..., y_{m} \right \}, 記 i, j 為序列的游標. 其中, i = 1, 2, ..., m, j = 1, 2, ..., m. 對於初始狀態, i = 1, j = 1

請閣下注意, 接下來所說的並不一定總是從初始狀態開始, 從任意中間狀態開始也適用

j' = j. 向右移動 i, 直到找到第一个使得 x_{i} > y_{j} 的元素为止; 然后, 向右移动 j, 直到找到第一个使得 y_{j} > x_{i} 的元素为止. 接著, 將子序列 \mathscr {E}_{i \rightarrow j} = \left \{ x_{i}, x_{i + 1}, ..., x_{n}, y_{j'}, y_{j' + 1}, ..., y_{j}, y_{j + 1}, ..., y_{n} \right \} 向右旋轉 j' - j 個位置即可

首先把 i 向右移動五個元素, 找到第一個大於 2 的元素 :

然後把 j 向右移動三個元素, 找到第一個大於 3 的元素 :

接著把序列 {3, 4, 2, 2, 3, 4} 向右旋轉 j - j' = 3 個元素, 並且移動 j' 即可 :

最後, 我們來分析一下旋轉的時間複雜度, 其空間複雜度顯然是 O(1), 因為它需要的辅助空間和元素數量沒有任何關係, 是常數級別的. 不論是否要進行移動, 我們總是需要尋訪幾乎整個序列 (若右側序列已經尋訪完畢, 那麼若前面還有元素沒有尋訪完, 也可以提前終止), 此處需要 O(n) 的時間. 每一次移動元素的數量比定不是 n 個元素, 但是也不低於 1 個, 故此處不妨假設平均需要移動 O(\log {n}) 個元素, 那麼需要 O(\log {n}) 的時間. 若序列本身已經有序, 那麼並不需要進行移動, 而最壞的情況下, 每走一步就需要進行一次移動, 因此至多需要移動的總次數為 O(n \log {n}), 其總的時間複雜度為 O(n \log {n}). 綜上所述, 使用了旋轉進行合併的合併排序, 其時間複雜度可以保持在 O(n \log {n}) 級別. 但是很顯然, 這個比使用了額外空間進行輔助的合併排序要慢一些, 差別為常數級別, 因此複雜度並沒有體現出這一點

下面僅給出空間複雜度為 O(1) 的合併排序版本 :

void merge_sort(int *begin, int *end) {
    const auto size {end - begin};
    switch(size) {
        case 2:
            if(*begin >= *(begin + 1)) {
                std::swap(*begin, *(begin + 1));
            }
        case 1:
        case 0:
            return;
        default:
            break;
    }
    const auto mid {begin + (size / 2)};
    merge_sort(begin, mid);
    merge_sort(mid, end);
    for(auto i {begin}, j {mid}; j not_eq end;) {
        do {
            if(*j < *i) {
                break;
            }
        }while(++i not_eq j);
        auto middle {j};
        do {
            if(*i < *j) {
                break;
            }
        }while(++j not_eq end);
        std::rotate(i, middle, j);
    }
}

對於泛型的實作方式, 可以參考本人的 GitHub : GitHub 點擊直達, 搜尋 merge_sort