多線程排序C++怎麼實現才是編寫效率和運行效率都很高的方案？

多線程排序C++怎麼實現才是編寫效率和運行效率都很高的方案？

我覺得需要簡化一下問題：

首先常見的排序演算法比如QuickSort MergeSort都是O(nlogn)的複雜讀，問題是採用k個線程，能否優化到O(nlogn / k) 這個複雜度？比如把QuickSort中的partition操作並行化？

---

我的書第12.8.3節。

再給幾個種子：

• Sort Benchmark Home Page
• AlphaSort
• The influence of caches on the performance of sorting

---

我就說快速排序，有且只有通過prefix sum可以實現parallel，優化pivot selection後，時間複雜度是O(n/p*logn + log^2(p))

這個log^2(p)說明了三件事：

1. communication overhead是這麼大
2. 如果我們用n個core去sort，那麼最終得到的時間複雜度是O(log^2(n))，就不再cost-optimal了
3. 在實際使用中，通常communication cost會dominate

---

對並行演算法了解的不多，覺得可以參考一下當年的排序網路（Sorting network），排序網路以前用於設計並行排序硬體設備，它只依賴一種叫做比較器的簡單元器件。

利用雙調排序網路（Bitonic sorter）構造出一個並行化的排序演算法應該不難，雙調排序網路的結構比較簡單而且優美，實現各個核之間的同步感覺會比較容易。雙調排序網路的深度是O((lgn)^2)，所以如果有p個核的話構造出來的並行排序複雜度應該是O(n/p*(lgn)^2)，當n=p時就變成和樓上一樣的O((lgn)^2)。

記得還有一個逆天的AKS排序網路可以做到漸進最優的O(lgn)的深度，用這個網路來構造的話估計n個核可以做到O(n/p*lgn)的複雜度了，不過常數因子也很大，估計要幾千（原始論文複雜得不能理解）。

哦，程序的編寫效率么，可以考慮用雙調排序網路，既美觀效率也不差，數據的中間比較結果不會改變原有程序的執行過程（其實只要數據量是一定的，每個核執行的操作都是固定的，不會因為數據的改變而改變），而且數據有序與否不影響運行效率，如果願意，可以寫成原地排序。

當然在實際使用過程中，並行演算法還是應該看實際的運行效率決定用哪種。

---

https://github.com/1d7500/trunk/blob/master/example/java7example/src/main/java/com/java7developer/example/FastSort.java

學forkjoin框架時寫的例子

---

第一反應是快排。。

這一定是病

---

推薦閱讀：