優化Mergesort

Question

合併排序是一種相當常見的排序算法，我寫了一個工作的合併排序算法。然後我想優化它。第一步是將其從遞歸轉換爲迭代，我就是這樣做的。然後我看不出還有什麼可以優化的。經過網絡上的大量文章，我得到了兩個機制，使用多合併排序和平鋪合併排序。然而，沒有任何文件提供任何僞代碼，甚至不關心如何去做，以及它如何提供其作者所說的優點，如緩存友好和改進的局部性。

任何人都可以詳細說明這個問題，如果可能的話，提供一些僞代碼？具體來說，我想知道如何讓它緩存友好。我完全不知道這些東西是什麼，否則我會自己嘗試。

Answer 1

您可以進行的一種常見且相對直接的優化方式是，當子陣列大小低於某個閾值時，從mergesort切換到另一種算法，如插入排序。雖然mergesort運行時間爲O（n log n），但它談到了它的長期增長率，並沒有說明算法在小輸入上表現如何。例如，插入排序在小輸入尺寸下運行速度非常快，即使長期運行情況更糟糕。因此，考慮更改mergesort的基本大小寫，以便如果要排序的數組低於某個大小閾值（例如50-100），則使用插入排序而不是繼續遞歸。從經驗來看，這可以顯着提高算法的性能。