爲什麼合併排序比正常排序列表排序更快？

我正在做一個基於比較的合併分析算法，它按照升序輸出。我注意到它是更快（比較少），當我給它一個反向排序列表，而不是升序排序列表。有人可以解釋爲什麼嗎？爲什麼合併排序比正常排序列表排序更快？

來源

2012-08-28 Scott Mullaly

http://stackoverflow.com/q/11227809/758280 – Jeffrey

@Jeffrey我假設他正在計算比較的次數（他寫的「比較少」），這應該排除分支預測。 –

我其實只是有同樣的情況，其中比較的數量恰好是在倒序數組上的數組長度。隨機數組和排序數組的比較次數遵循n（log（n））模式。 –

您的排序代碼中必須有錯誤。

根據我的理解，通過文字MergeSort執行的比較次數應該是獨立的的數據。這意味着它不能比O(n log n)差，但也不會更好（除非你做了一些聰明的修改，比如在「自然mergesort」或TimSort中）。

來源

2012-08-28 22:05:50

要合併兩個長度爲M和N的列表，最多需要M + N-1個比較。如果第一個列表中的所有條目都小於第二個列表中的條目，則只需要M個比較。如果第二個列表中的所有條目都小於第一個列表中的條目，則只需要N個比較。

如果您正在排序的總數量不是2的效價，那麼您將遇到將您劃分爲兩個不同長度的列表的情況。我懷疑你實現了合併排序的方式，其中第一個有更多的元素。這意味着對於該分區和合並，M = N + 1。如果元素的順序相反，則第二個列表中的所有元素都將小於第一個列表中的元素，並且在正確順序的情況下，您需要N個比較而不是M個比較。

如果你想排序的列表是2的效價，正常順序和逆序之間應該沒有區別。

來源

2015-05-17 13:17:52

爲什麼合併排序比正常排序列表排序更快？

回答

相關問題