摘要訊息 : 使用分而治之演算法進行排序.

0. 前言

分而治之演算法 (《分而治之演算法》) 同樣也可以被用於排序當中, 很自然地可以得到一個全新的排序演算法.

本篇文章中, 我們主要討論的是升序的合併排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.

更新紀錄 :

• 2022 年 5 月 27 日進行第一次更新和修正.

1. 分而治之

分而治之演算法要求解決子問題的時間複雜度一般是 \Theta(1) 的. 根據集合的特點, 當元素數量 n = 0 或者 n = 1 時, 無需進行排序; 當 n = 2 時, 可以通過交換來排序, 此時的時間複雜度為 \Theta(1); 當 n > 2 時, 我們就很難在 \Theta(1) 的時間複雜度內完成排序. 因此我們制定的分治策略應該是當每一個子集合中的元素數量 n 都滿足 n \leq 2 時停止劃分集合; 當 n > 2 時就把集合一分為二, 分成兩個子集合.

例題 1. 使用分治策略對 \mathscr {S} = \left \{ 7, 3, 6, 1, 9, 0, 3, 2, 4 \right \} 進行劃分.

解 :

由於 \mathop {\mathrm {card}} {\mathscr {S}} = 9 > 2, 因此將集合一分為二, 得到 S_{1} = \left \{ 7, 3, 6, 1 \right \} 和 S_{2} = \left \{ 9, 0, 3, 2, 4 \right \}.

由於 \mathop {\mathrm {card}} {S_{1}} = 4 > 2, 繼續對其進行劃分, 得到 S_{11} = \left \{ 7, 3 \right \} 和 S_{12} = \left \{ 6, 1 \right \}. 由於 \mathop {\mathrm {card}} {S_{2}} = 5 > 2, 繼續進行劃分得到 S_{21} = \left \{ 9, 0 \right \} 和 S_{22} = \left \{ 3, 2, 4 \right \}.

現在, \mathop {\mathrm {card}} {S_{11}} = \mathop {\mathrm {card}} {S_{12}} = \mathop {\mathrm {card}} {S_{21}} = 2, 所以無需繼續進行劃分. 但是 \mathop {\mathrm {card}} {S_{22}} = 3 > 2, 所以還要對其進行劃分, 得到 S_{221} = \left \{ 3 \right \} 和 S_{222} = \left \{ 2, 4 \right \}.

最終, S_{11}, S_{12}, S_{21}, S_{221} 和 S_{222} 都滿足集合中元素數量至多為兩個且 \displaystyle {\mathscr {S} = S_{11} \cup S_{12} \cup S_{21} \cup S_{221} \cup S_{222}}.

\blacksquare

例題 2. 對例題 1 中得到的子集合 S_{11} = \left \{ 7, 3 \right \}, S_{12} = \left \{ 6, 1 \right \}, S_{21} = \left \{ 9, 0 \right \}, S_{221} = \left \{ 3 \right \} 和 S_{222} = \left \{ 2, 4 \right \} 分別進行排序.

解 :

由於 S_{11} 並非升序, 因此交換集合的兩個元素的到 S_{11} = \left \{ 3, 7 \right \}; S_{12} 並非升序, 因此交換集合的兩個元素的到 S_{12} = \left \{ 1, 6 \right \}; S_{21} 並非升序, 因此交換集合的兩個元素的到 S_{21} = \left \{ 0, 9 \right \}; S_{221} 只有一個元素, 所以無需排序; S_{222} 本身有序.

\blacksquare

2. 合併

現在, 我們面臨如何將例題 2 中各個有序的子集合合併為有序的大集合的問題. 以 S_{11} 和 S_{12} 為例. 我們完全可以以 S_{11} 為基準, 把 S_{12} 中的元素通過比較插入的方式合併到 S_{11} 中. S_{12} 中的元素 1 比 S_{11} 中的元素 3 要小, 所以合併之後應該有 S_{11} = \left \{ 1, 3, 7 \right \}. 對於 S_{12} 中的元素 6 來說, 滿足 3 < 6 < 7, 因此合併之後應該有 S_{11} = \left \{ 1, 3, 6, 7 \right \}.

合併的方式不只是上面這一種, 我們可以令 S = S_{11} \cup S_{12} = \left \{ 3, 7, 1, 6 \right \}, 然後從 S_{12} 的首個元素 1 開始, 以氣泡的形式向上冒. 由於 1 < 7, 所以元素 1 向左移動一個位置, 得到 S = \left \{ 3, 1, 7, 6 \right \}; 由於 1 < 3, 所以元素 1 向左移動一個位置, 得到 S = \left \{ 1, 3, 7, 6 \right \}. 接下來輪到 6, 由於 6 < 7, 所以元素 6 向左移動一個位置, 得到 S = \left \{ 1, 3, 6, 7 \right \}; 由於 6 > 3 , 所以 S 已經有序.

我們還可以借助輔助空間的方式. 一開始令 S = \emptyset. 然後通過不斷比較 S_{11} 和 S_{12} 中第一個元素, 誰小誰就能先進入集合 S. 剛開始, S_{12} 中的元素 1 比 S_{21} 中的元素 3 大, 所以 1 先進入 S, 得到 S = \left \{ 1 \right \}. 接下來由於 S_{11} 中的首個元素 3 比 S_{21} 中的首個元素 6 小, 所以 3 進入 S, 得到 S = \left \{ 1, 3 \right \}. 然後由於 S_{12} 中的首個元素 6 比 S_{11} 中的首個元素 7 小, 所以 6 進入 S, 得到 S = \left \{ 1, 3, 6 \right \}. 此時, S_{12} 中已經沒有元素了, 說明 S_{11} 中的剩餘元素都比 6 大, 而 S_{11} 中的剩餘元素本身就是有序的, 所以可以直接把 S_{11} 中的聲譽元素放入 S. 最終有 S = \left \{ 1, 3, 6, 7 \right \}.

我們討論的三種合併方式中, 第一種方式和第二種方式其實是有跡可循的, 即插入排序法 (《【演算法】插入排序法 (Insertion Sort)》) 和氣泡排序法 (《【演算法】氣泡排序法 (Bubble Sort)》). 這兩種方法雖然空間複雜度為 \Theta(1), 但是時間複雜度是 \Theta(n^{2}). 第三種借助輔助空間的方法雖然時間複雜度下降到了 \Theta(n), 但是空間複雜度卻上升到了 \Theta(n), 屬於空間換時間的做法. 那麼是否可能有一種方式, 使得合併的時間複雜度降低一些, 同時保持空間複雜度為 \Theta(1) 呢?

借助旋轉 (《【資料結構】向量 (順序表)》第 6 節), 我們可以把合併的空間複雜度保持在 \Theta(1), 同時將時間複雜度降低到 \Theta(n\log {n}). 原理也很簡單, 在向量中的每一次旋轉的時間複雜度都是 \Theta(n) 且空間複雜度都是 \Theta(1), 如果我們能夠進行 \Theta(\log {n}) 次旋轉, 那麼就可以把時間複雜度降低至 \Theta(n\log {n}), 空間複雜度保持 \Theta(1).

令向量 \mathscr {S} = \left \{ x_{1}, x_{2}, ..., x_{m - 1}, x_{m}, x_{m + 1}, x_{m + 2}, ..., x_{n} \right \}. 其中, x_{1} \leq x_{2} \leq ... \leq x_{m - 1} \leq x_{m}, x_{m + 1} \leq x_{m + 2} \leq ... \leq x_{n}, m = \left \lfloor \frac {n}{2} \right \rfloor. 也就是說, x_{m} 和 x_{m + 1} 實際上將向量 \mathscr {S} 的有序性由此分隔開來.

一開始令 i = 1, j' = j = m + 1. 我們的目的是找到一個 x_{i} 使得 x_{i} > x_{j} 成立. 因此, 這個時候我們只需要不斷向右搜尋即可, 這個過程中 i 可能會不斷遞增, 每次遞增的幅度為 1. 在找到一個 x_{i} 使得 x_{i} > x_{j} 成立之後, 我們以相同的方式從 x_{j} 開始向右搜尋, 目的也是找到一個 x_{j} > x_{i}. 一旦遇到 j = n + 1, 搜尋就停止, 說明這個向量不需要旋轉便已經有序. 一旦 i 和 j 都確定之後, 對子向量 \left \{ x_{i}, x_{i + 1}, ..., x_{j - 1} \right \} 向右旋轉 j - j' 個元素. 如果此時 j \neq n + 1, 則說明向量可能還沒有完全有序, 令 j' = j, 然後必須再進行類似的過程, 直到 j = n + 1 為止. 這個過程中, 要注意更新 j'.

例題 3. 使用 Algorithm 1 對例題 2 得到的所有有序子集合進行合併.

解 :

首先對子集合 S_{11} = \left \{ 3, 7 \right \} 和 S_{12} = \left \{ 1, 6 \right \} 進行合併. 記 S_{1} = \left \{ 3, 7, 1, 6 \right \}, 令 i = 1, j = 3 及 j' = 3.

由於 3 \leq 1 不成立, 所以 i 的值不變. 接下來考慮 j. 因為 1 \leq 3 成立, 所以令 j 加一, 即 j = 4; 因 4 \leq 3 不成立, 所以 j 的值不再變化.

此時, 我們將子向量 \left \{ 7, 3, 6 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉一個元素.

由於 j \neq 5, 說明這個集合還未確定有序. 更新 j' = j = 4. 向右搜尋並且更新 i 找到元素 7 滿足 7 \leq 6 不成立, 此時 i = 3. 向右更新 j 的時候發現 j = 5, j 已經超出了集合中元素的數量, 所以不再更新 j.

將子向量 \left \{ 7, 6 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉一個元素.

由於 j 已經超出了集合中元素的數量, 所以 S_{1} = \left \{ 1, 3, 6, 7 \right \} 已經有序.

記 S_{2} = \left \{ 3, 2, 4 \right \} 是對 S_{221} 和 S_{222} 的合併. 令 i = 1, j' = j = 2.

由於 3 \leq 2 不成立, 所以 i 的值不變. 接下來考慮 j. 因為 2 \leq 3 成立, 所以令 j 加一, 即 j = 3; 因 4 \leq 3 不成立, 所以 j 的值不再變化.

此時, 我們將子向量 \left \{ 3, 2 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉一個元素.

由於 j \neq 4, 說明這個集合還未確定有序. 更新 j' = j = 3. 向右搜尋並且更新 i 找到元素 4 時, 有 i = j = 3. 此時, 停止更新 i. 向右更新 j 的時候發現 j = 4, j 已經超出了集合中元素的數量, 所以不再更新 j.

此時, 我們將子向量 \left \{ 4 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉一個元素. 然而, 這個子向量只有一個元素, 所以根本不需要進行旋轉. 由於 j 已經超出了集合中元素的數量, 所以 S_{2} = \left \{ 2, 3, 4 \right \} 已經有序.

記 S_{3} = \left \{ 0, 9, 2, 3, 4 \right \} 是對 S_{21} 和 S_{2} 的合併. 令 i = 1, j' = j = 3.

以 i 開始向右搜尋發現元素 9 不滿足 9 \leq 2, 因此停止更新 i, 此時 i = 2. 接下來考慮 j. 向右搜尋直到 j = 6 時仍然沒有發現大於 x_{i} = 9 的元素, 此時 j 已經超出了集合中元素的數量, 停止更新 j.

將子向量 \left \{ 9, 2, 3, 4 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉三個元素.

由於 j 已經超出了集合中元素的數量, 所以 S_{3} = \left \{ 0, 2, 3, 4, 9 \right \} 已經有序.

最後, \mathscr {S} = \left \{ 1, 3, 6, 7, 0, 2, 3, 4, 9 \right \} 是 S_{1} 和 S_{3} 合併的結果. 令 i = 1, j' = j = 5.

由於 1 \leq 0 不成立, 所以 i 不進行更新. 接下來考慮 j. 向右搜尋發現 2 \leq 1 不成立, 此時 j = 6.

將子向量 \left \{ 1, 2, 6, 7, 0 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉一個元素.

更新 i = 2, j' = j = 6. 向右搜尋發現 3 \leq 2 不成立, 此時 i = 3. 接下來考慮 j. 向右搜尋發現 4 \leq 3 不成立, 此時 j = 8.

將子向量 \left \{ 3, 6, 7, 2, 3 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉兩個元素.

更新 i = 5, j' = j = 8. 向右搜尋發現 6 \leq 4 不成立, 此時 i = 6. 接下來考慮 j. 向右搜尋發現 9 \leq 6 不成立, 此時 j = 9.

將子向量 \left \{ 6, 7, 4 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉一個元素.

更新 i = 7, j' = j = 9. 一直向右搜尋直到 i = j = 9, 都沒有發現滿足 x_{i} \leq x_{j} 不成立的元素, 此時停止更新 i, 考慮 j. 向右搜尋直到 j = 10 時, 由於j 已經超出了集合中元素的數量, 所以停止更新 j.

將子向量 \left \{ 9 \right \} 向右旋轉 j' - j 個元素, 即向右旋轉三個元素. 然而, 這個子向量只有一個元素, 所以根本不需要進行旋轉.

最終, \mathscr {S} = \left \{ 0, 1, 2, 3, 3, 4, 6, 7, 9 \right \} 有序. 我們對例題 1 中的 \mathscr {S} 的合併排序完成.

\blacksquare

3. 合併排序法

我們把利用 Algorithm 1 的 Algorithm 2 成為合併排序法 (merge sort).

3.1 穩定性討論

由 Algorithm 1 進行合併操作的合併排序法並不是一個穩定的排序演算法. 嚴格地說, 在排序之後, 原來正序排列的相同元素在演算法完成之後中會倒序排列. 這因為在 Algorithm 1 中的第五行和第十一行中, 我們採用的是 \leq 進行比較. 如果我們把等號去掉, 那麼這個合併操作驅動的合併排序便是一個穩定的排序演算法.

3.2 複雜度分析

合併排序法的空間複雜度嚴格來說是 \Theta(\log {n}), 因為在 Algorithm 2 中, 我們使用了遞迴. 遞迴會一直進行到 n \leq 2 才停止. 所以總共需要 \left \lceil \log_{2}{n} \right \rceil 次遞迴, 每一次都需要儲存參數的話, 空間複雜度便是 \Theta(\log {n}).

3.2.1 不採用旋轉合併

合併排序法採用了分而治之演算法, 所以其時間複雜度分析可以採用分而治之演算法的通用時間複雜度分析公式 (《分而治之演算法》) \displaystyle {T(n)= \begin{cases} \Theta(1) & {n \leq c} \\ aT \left ( \frac {n}{b} \right ) + D(n) + C(n) & {n > c}. \end{cases}} 來進行. 在合併排序法中, 當 n \leq 2 時, 合併排序法可以在常數時間完成, 所以 c = 2. 一般來說, 合併排序法會採用一分為二的分治策略, 因此 b = 2. 一分為二這個操作本身不需要額外的時間, 可以在常數時間內完成, 故 D(n) = \Theta(1). 一分為二之後, 兩側的子集合各自獨立處理, 所以總共需要處理兩次, 故 a = 2. 所以合併排序法的時間複雜度應該可以寫成 \displaystyle {T(n)= \begin{cases} \Theta(1) & {n \leq 2} \\ 2T \left ( \frac {n}{2} \right ) + \Theta(1) + C(n) & {n > 2}. \end{cases}} 然而, \frac {n}{2} 並不一定總是整數, 所以準確來說, 應該將 T(n) 寫成 \displaystyle {T(n)= \begin{cases} \Theta(1) & {n \leq 2} \\ T \left ( \left \lfloor \frac {n}{2} \right \rfloor \right ) + T \left ( n - \left \lfloor \frac {n}{2} \right \rfloor \right ) + \Theta(1) + C(n) & {n > 2}. \end{cases}}

為了確定 C(n), 我們還需要分析合併所需要的時間複雜度. 在第 2 節中, 我們給出了插入合併, 泡沫合併, 輔助空間合併和旋轉合併四種合併方案. 顯然, 如果採用插入合併或者泡沫合併, 則 C(n) = \Theta(n^{2}). 如果採用輔助空間合併, 則 C(n) = \Theta(n).

不是一般性, 我們設 n 為偶數. 對於不是偶數的 n, 我們可以向集合中添加一個元素使得 n 為偶數. 記 n = 2^{k}, 對於採用插入合併或者泡沫合併的合併排序法時間複雜度, 我們可以通過計算遞迴方程式 (《【遞迴方程式】替代法與歸納法》) \displaystyle {T(n)= \begin{cases} \Theta(1) & {n \leq 2} \\ 2T \left ( \frac {n}{2} \right ) + \Theta(n^{2}) & {n > 2}, \end{cases}} 得到 \displaystyle {\begin {aligned} T(n) &= T(2^{k}) = 2T(2^{k - 1}) + \Theta(n^{2}) \\ &= 2 \left ( T(2^{k - 2}) + \Theta(n^{2}) \right ) + \Theta(n^{2}) \\ &= 2T(2^{k - 2}) + 2\Theta(n^{2}) + \Theta(n^{2}) \\ &= 2T(2^{k - 3}) + 2 \cdot 2 \Theta(n^{2}) + \Theta(n^{2}) \\ &= ... \\ &= 2T(2) + 2(k - 1)\Theta(n^{2}) + \Theta(n^{2}) \\ &= \Theta(1) + (2k - 1)\Theta(n^{2}) \\ &= (2k - 1)\Theta(n^{2}). \end {aligned}} 由於 n = 2^{k}, 故 k = \log_{2}{n}, 因此有 \displaystyle {T(n) = (2k - 1)\Theta(n^{2}) = \Theta(k) \cdot \Theta(n^{2}) = \Theta(\log {n}) \cdot \Theta(n^{2}) = \Theta(n^{2}\log {n}).} 對於採用輔助空間合併的合併排序法時間複雜度, 我們可以通過計算遞迴方程式 \displaystyle {T(n)= \begin{cases} \Theta(1) & {n \leq 2} \\ 2T \left ( \frac {n}{2} \right ) + \Theta(n) & {n > 2}, \end{cases}} 得到 \displaystyle {\begin {aligned} T(n) &= T(2^{k}) = 2T(2^{k - 1}) + \Theta(n) \\ &= T(2^{k - 2}) + 2\Theta(n) + \Theta(n) \\ &= ... \\ &= 2T(2) + 2(k - 1)\Theta(n) + \Theta(n) \\ &= (2k - 1)\Theta(n) \\ &= \Theta(k) \cdot \Theta(n) = \Theta(\log {n}) \cdot \Theta(n) \\ &= \Theta(n\log {n}). \end {aligned}}

最重我們可以得到, 採用插入合併或者泡沫合併的合併排序法的時間複雜度為 \Theta(n^{2}\log {n}), 採用輔助空間合併的合併排序法的時間複雜度為 \Theta(n\log {n}).

3.2.2 從哪裡劃分?

為了分析採用旋轉合併的合併排序法的時間複雜度, 即以 Algorithm 1 驅動的合併排序法的時間複雜度, 我們還需要討論一個問題. 在第 1 節和第 2 節我們都默認了從中間一分為二這個事實. 但是從中間一分為二就是最好的劃分方案嗎? 會不會存在更好的方案?

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

證明 :

令 z = y - d, 替換可得 \displaystyle {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} 代入, 得 \displaystyle {2f \left ( \frac {r}{2} \right ) \leq f \left ( \frac {r}{2} + \frac {r}{2} \cdot \frac {r}{c} \right ) + f \left ( \frac {r}{2} - \frac {r}{2} + \frac {r}{c} \right )}, 即 \displaystyle {2f \left ( \frac {r}{2} \right ) \leq f \left ( r - \frac {r}{c} \right ) + f \left ( \frac {r}{c} \right )}. 當 c < 2 時, 將 d = \frac {r}{c} - \frac {r}{2} 和 y = \frac {r}{2} 代入, 得 \displaystyle {2f \left ( \frac {r}{2} \right ) \leq f \left ( \frac {r}{2} + \frac {r}{c} - \frac {r}{2} \right ) + f \left ( \frac {r}{2} - \frac {r}{c} + \frac {r}{2} \right )}, 即 \displaystyle {2f \left ( \frac {r}{2} \right ) \leq f \left ( \frac {r}{c} \right ) + f \left (r - \frac {r}{c} \right )}. 於是有 2f \left ( \frac {r}{2} \right ) \leq f \left (r - \frac {r}{c} \right ) + f \left (\frac {r}{c} \right ). 換言之, f \left ( r - \frac {r}{2} \right ) + f \left ( \frac {r}{2} \right ) \leq f \left ( r - \frac {r}{c} \right ) + f \left ( \frac {r}{c} \right ).

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

\blacksquare

引理 1 對於任意實數 r 都成立, 自然對於任何非負整數 n 也成立. 不妨假設 n 滿足 n = 2^{k}. 對於 n 不滿足 n = 2^{k} 的情形, 我們可以通過適當擴大 n 使得其滿足 n = 2^{k}. 其中, k 為非負整數. 那麼對於分而治之演算法的時間複雜度 2T \left ( \frac {n}{2} \right ) \leq T \left ( \frac {n}{b} \right ) + T \left ( n - \frac {n}{b} \right ), 顯然當 b = 2 時才能夠讓 T \left ( \frac {n}{b} \right ) + T \left ( n - \frac {n}{b} \right ) 取得最小值, 即從中間劃分就是最好的方案.

3.2.3 採用旋轉合併

現在, 我們來分析採用旋轉合併的合併排序法的時間複雜度. 根據分而治之演算法的時間複雜度 T(n) 的表示, 我們已經可以得到採用旋轉合併的合併排序法的時間複雜度可以表示為 T(n) = 2T \left ( \frac {n}{2} \right ) + \Theta(1) + C(n). 關鍵是得到 C(n). 我們仍然採用第 3.2.2 節中對 n 的假設, 認為 n 滿足 n = 2^{k}. 其中, k 為非負整數.

對於合併, 旋轉至多進行 \Theta(\log {n}) 次, 每一次旋轉的時間複雜度為 \Theta(n) (參考《【資料結構】向量 (順序表)》第 6.2 節最後的時間複雜度分析), 所以 C(n) = \Theta(n\log {n}). 那麼計算遞迴方程式 \displaystyle {T(n)= \begin{cases} \Theta(1) & {n \leq 2} \\ 2T \left ( \frac {n}{2} \right ) + \Theta(n\log {n}) & {n > 2}, \end{cases}} 得到 \displaystyle {\begin {aligned} T(n) &= T(2^{k}) = 2T(2^{k - 1}) + \Theta(n\log {n}) \\ &= 2T(2^{k - 2}) + 2\Theta(n\log {n}) + \Theta(n\log {n}) \\ &= ... \\&= 2T(2) + 2(k - 1)\Theta(n\log {n}) + \Theta(n\log {n}) \\ &= \Theta(1) + \Theta(k) \cdot \Theta(n\log {n}) \\ &= \Theta(\log {n}) \cdot \Theta(n\log {n}) \\ &= \Theta(n\log^{2}{n}). \end {aligned}}

綜上所述, 採用旋轉合併的合併排序法的時間複雜度為 \Theta(n\log^{2}{n}).

值得一提的是, 一般在使用合併排序法的時候, 我們都會使用額外的輔助空間進行合併. 只有要求空間複雜度為 \Theta(1) 的情況下, 我們才使用採用旋轉合併的合併排序法. 另外, 目前應該還不存在合併操作的空間複雜度為 \Theta(1) 但是時間複雜度為 \Theta(n\log {n}) 的合併排序法.

4. 實作

#include <algorithm>

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);
    }
}

這個實作版本並沒有採用 Algorithm 1 的合併, 所以排序的結果具有穩定性. 對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 merge_sort 即可.