在排序固定長度的小陣列時，那些 big-O 優異的演算法往往討不到便宜，而且還很容易因為多餘的操作而拖慢速度。Sorting Network 就是為了排序固定長度的小陣列而發明的。Sorting Network 是一組事先規劃好的比較、交換操作，只要按照固定步驟操作就能將資料排序。
若一個 Sorting Network 滿足某些條件，就可以將操作步驟平行化或者實作成平行排序硬體，這是這類演算法最大的優勢，不過這不是本文的重點。即使在沒有平行化的情況下，Sorting Network 作為循序執行的排序法效能通常也不錯，至少可以狂電 Bubble、Insertion sort，而且所有的動作都是固定的，可以輕易寫成一連串無迴圈的 if-swap 串，這在「big-O不代表一切」的小資料世界裡具有實作優勢。
有一些演算法可以系統化產生 Sorting Network，例如 Bose-Nelson、Batcher's odd–even mergesort、Bitonic 等等。一般如果要寫 Sorting Network 程式，比較簡單的方法是 先用這些演算法產生比較序列 ，然後再手工刻出一堆 if-swap 串。例如：
void sort_int6(int* arr)
{
#define CMP_SWAP(i, j) \
if (arr[j] < arr[i]) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
CMP_SWAP(1, 2);
CMP_SWAP(0, 2);
CMP_SWAP(0, 1);
CMP_SWAP(4, 5);
CMP_SWAP(3, 5);
CMP_SWAP(3, 4);
CMP_SWAP(0, 3);
CMP_SWAP(1, 4);
CMP_SWAP(2, 5);
CMP_SWAP(2, 4);
CMP_SWAP(1, 3);
CMP_SWAP(2, 3);
#undef CMP_SWAP
}
這些系統化方法產生出來的步驟並非對所有輸入長度都是最佳，所以有一些人專門在尋找針對某個特定長度的最佳排序步驟，他們使用的方法包括暴力解、演化式演算法等等。至於斤斤計較幾個操作是否具有實用價值，我就不清楚了。
要證明某個 Sorting Network 是否是某個長度的最佳排序步驟其實並不是件容易的事，Knuth 在 《Art of Computer Programming》提過一個在輸入長度 16 時，depth 最優的演算法，Knuth 和 Floyd 在 1960 年代就已經做過部份證明，然而完整的證明直到 2014 年才出爐。
圓規正轉，我想到既然有系統化的生成演算法，那應該可以用 C++ template 實作，讓編譯器幫我們規劃比較與交換的序列，於是就寫了個小程式來玩玩看。使用的方法大概是這樣：
std::array<int, 8> intArray = {...};
std::array<string, 8> strArray = {...};
FixedSort<8> sort8; // sorting network for size 8.
sort8(intArray.data());
sort8(strArray.data());
以下只是概念驗證的實作，並沒有考慮太多細節：
// Generate sorting network using Bose-Nelson algorithm.
template <int J, int K>
struct CompareSwap
{
template <typename T>
inline static void apply(T* array)
{
if (array[J] > array[K]) {
std::swap(array[J], array[K]);
}
}
};
template <int J, int LenJ, int K, int LenK>
struct Merge
{
enum {
MidJ = LenJ / 2,
MidK = (LenJ & 1) ? LenK / 2 : (LenK + 1) / 2
};
template <typename T>
inline static void apply(T* array)
{
Merge<J, MidJ, K, MidK>::apply(array);
Merge<J + MidJ, LenJ - MidJ, K + MidK, LenK - MidK>::apply(array);
Merge<J + MidJ, LenJ - MidJ, K, MidK>::apply(array);
}
};
template <int J, int K>
struct Merge<J, 1, K, 1>
{
template <typename T>
inline static void apply(T* array)
{
CompareSwap<J, K>::apply(array);
}
};
template <int J, int K>
struct Merge<J, 1, K, 2>
{
template <typename T>
inline static void apply(T* array)
{
CompareSwap<J, K+1>::apply(array);
CompareSwap<J, K>::apply(array);
}
};
template <int J, int K>
struct Merge<J, 2, K, 1>
{
template <typename T>
inline static void apply(T* array)
{
CompareSwap<J, K>::apply(array);
CompareSwap<J+1, K>::apply(array);
}
};
template <int Start, int Len>
struct Split
{
enum { Mid = Len / 2 };
template <typename T>
inline static void apply(T* array)
{
Split<Start, Mid>::apply(array);
Split<Start + Mid, Len - Mid> ::apply(array);
Merge<Start, Mid, Start + Mid, Len - Mid>::apply(array);
}
};
template <int Start>
struct Split<Start, 1>
{
inline static void apply(void* array) {}
};
template <int Len>
struct FixedSort
{
// static_assert(Len >= 2 && Len <= 16, "Len must between [2, 16]");
template <typename T>
inline void operator()(T* array)
{
Split<0, Len>::apply(array);
}
};
然後我用 6 ~ 16 長度的整數陣列測試執行時間，雖然事先已經預期會比 std::sort() 還快，但我完全沒想到在長度 8 的時候 FixedSort 耗時竟然只有 g++ 內建 std::sort() 的 1/15，在其他長度大概都比 std::sort() 快個 4 ~ 10 倍。（這裡有個有趣的錯誤，見補充）
實際觀察 FixedSort 用 g++ -O2 所生成的 x86 和 x86_64 組合語言，所有的函數全部被 inline，因此等效於一連串無迴圈的 if-swap。（組合語言這裡就不附了，有興趣的讀者可以自己玩玩看。）
我個人沒有根據的胡亂猜測，FixedSort 之所以比 g++ 內建的 std::sort() 還快，可能之一是 libstdc++ 在小陣列優化不足。而 FixedSort 則因迴圈攤平得到許多好處，特別是現代的處理器的分支預測、指令層級平行能力。這只是猜想，實際原因我沒有去追蹤。
Bitonic 看起來似乎比 Bose-Nelson 更快一點點，或許可以找個時間來實作看看。
2016-mar-06 補充：
由於效能差距太可疑了，我今天重新做了實驗，奇怪的是將 array 改成 vector 之後，差距變得合理多了，FixedSort 耗時大約是 std::sort 的 60%~90% 左右。
不確定之前的差距所在，不太像是邏輯錯誤，因為我也只是把之前的程式碼改 type 而已，而且我有用 std::is_sorted() 檢查過排序正確性。
再補充：找到原因了，其實還蠻好笑的。我在測試正確性的時候用的是完整的 std::is_sorted()，但是測效能時為了減少干擾，只檢查首末兩項的 checksum。
好玩的地方在於當 g++ 把所有的東西 inline 進來後發現我們只關心首末兩項，所以就只把首末兩項排好，與首末兩項無關的程式碼都被丟棄。
參考資料：
留言列表
Computer (6)
