快速排序與歸併排序的多核並行化加速分析

核心結論

• 歸併排序極適合並行：分治階段天然無依賴，合併階段可並行歸併。JDK 8 Arrays.parallelSort 即基於此實現。
• 快速排序理論可並行：分區後左右子數組獨立，但分區質量不穩定（極端情況退化為 O(n^2)），導致負載不均，理論加速比難以保證。

實測數據（參考）

未達線性加速的主要原因：合併/分區階段的同步開銷 及 內存帶寬瓶頸。

建議

• 優先選擇歸併排序並行版本（如 JDK 8 parallelSort、C++17 std::parallel::sort）。
• 若必須用快排，採用隨機化樞軸 + 閾值切換插入排序，並限制並行深度（如僅前 logP 層並行）。
• 不要對並行排序抱有過高期望，工程上往往通過 外部排序 + 多路歸併 解決超大規模數據。