慘慘慘今天整個沒有時間...

今天來聊聊字組內任意順序的調換。這個動作對於排序的其中一步是相當重要的。
簡單來說，在字組內部排序的時候，我們想要依照某個順序重新整理資料。
如同前幾天的文章，我們可以在每一筆資料前面加上一個「標示位元」。我們今天的任務就是，如果這些標示位元寫起來像是： 00101011，那麼我們想要在重新調換位置後讓所有標示位元是 0 的資料出現在標示位元是 1 的資料前面。

要怎麼作到呢？如果我們用 divide and conquer 會很慘，因為我們無法預知調換的順序，因此就沒有辦法作到字組中的平行化了。但實際上，有一個有趣的方法可以幫我們達到這個目標，他叫做 Bitonic Sort：如果有兩個排好序的資料，我們可以用「類似合併排序法」的概念，先把後面那段反過來，變成一個山型的資料，接著兩兩位置比較，把小的換到前半段，再遞迴重新整理兩邊。我們用 0~9 的數字作為舉例，可能比較清楚：

02456678 跟 11356789 要合併排序：

先把後面那段反過來

02456678
98765311

我們會發現「大於」的關係會長得像

00001111

這時候我們把這個 mask 找出來，然後把第一個字組的那部份與第二個字組的那部份調換順序

02455311
98766678

你就可以把比較小的地方與比較大的地方整個分開了！然後再遞迴下去排序就可以了！
這些東西都可以平行計算，所以最後的複雜度就會是 ，有趣吧科科。