爲什麼我們不能在合併排序中劃分數組5次？

Question

在合併排序中，我們總是將數組分兩次。我們爲什麼不把它分成兩次？並且在堆排序和合並排序中哪一個更好？I

Answer 1

爲什麼不試試看。編寫一個合併排序，將其拆分爲5個而不是2個，並測試其性能。最好的學習方法是嘗試。

它對計算複雜度沒有影響，所以改進最多是一個常數因子。您將合併傳遞的數量減少了lg（5）≈2.3，但合併步驟現在需要一個優先級隊列，該優先級隊列比兩階段合併所使用的單一比較要​​慢2.3倍。

劃分爲2個以上的部分稱爲polyphase merge sort，當您需要最小化合並通道數時使用它。