前情提要

我們在這個模型中，假設了一個長度為 w-bit 的字組內可以儲存 k 個整數值，基於避免溢位、或互相影響的情形下，我們不妨假設每個數值前面都順便預留了若干位元、可以自由運用的空間。

昨天我們迅速討論了字組內資料調換與字組內排序，結論是：我們可以在 的時間內做完字組內排序；此外，如果字組內的數字順序如山型一般先遞增再遞減，那麼組內排序便只要 的時間。只能排 k 個數字有什麼用？如果能直接排所有數字會更有用呀！所以我們今天就來討論討論在同一個字組內塞很多數字的時候，可以怎麼排序～

合併排序法 Merge Sort

從任何演算法的教科書中，我們不難發現合併排序法的蹤跡：我們可以把資料先分成兩堆、把兩堆分別排序完畢，然後再利用「線性時間」合併兩組排好順序的資料。

我們可以把合併排序法的概念直接應用進來！讓我們快速複習合併排序法的三步驟～

• Divide: 把輸入的數字分成兩堆
• Conquer: 兩堆分別呼叫遞迴排序
• Combine: 把兩個排好序的陣列合併起來

對於字組來說，Divide 跟 Conquer 都很簡單，把字組隨意分兩半然後呼叫遞迴就好。真正困難的是 Combine――原因是我們無法像原本合併排序法那樣，一次只拿一個數字做比較，每一次拿起來就是 k 個數字啊...

如果利用昨天的 Bitonic Sort（山型資料排序），對於兩堆排好順序的字組們中，分別取出最小的字組，各自有 k 個數值（總共 2k 個），合併起來做 O(log k) 時間的字組內排序。然後，把比較小的 k 個數值拿出來、而比較大的那 k 個數值就塞回對應的序列裡，等待下一次拿出來比較。

分析

怎麼分析這個演算法呢？我們可以利用字組的總操作數來做估算。所有資料有 n/k 個字組。先考慮遞迴中止條件：若只剩下 1 個字組，那麼使用 的時間就可以做字組內排序。否則的話，對於輸入的字組數量 X，我們就花費 時間 Divide & Conquer，而 Combine 的時間就會是 。

寫成遞迴式就是 ，遞迴中止條件是 。因此解出來的時間複雜度是 。這個在 的時候是 。如果 k 可以大到 左右，那我們就得到一個 時間的演算法，比傳統 時間的合併排序來得快了。如果 k 能放更大，到 左右，那我們就得到一個 「線性」時間、基於數值比較的演算法！

討論

以上我們想要排序的是「小整數」，如果對於更一般的情形，每一個整數可能大到 w-bit，要怎進行排序？能不能利用位元運算作到比 更好的作法？您可能會說：唉呀，那不直接用桶子排序或位數排序法就好了嗎？但是那些 Radix Sort、Bucket Sort 其實使用的空間都不是 線性的！若要達到 線性空間的排序（與 w 無關），目前大家還不知道能不能真的作到線性時間。

但，神奇的是，目前已知能作到比 快了！目前 state-of-the-art 時間複雜度是 （非隨機演算法）。如果我們能使用隨機數的話，甚至可以作到 的時間！如果有機會我可以再分享給大家～