Mergesort對三個輸入數組進行排序

Question

合併算法通過重複比較兩個輸入數組中的最小元素，並將兩個輸入數組中的較小元素移至輸出，將兩個排序後的輸入數組合併到排序後的輸出數組中。

現在我們需要相同長度的3個排序輸入陣列（A1，A2，和A3）合併爲一個（排序）輸出陣列，並且有兩種方法：

1. 使用上述合併算法將A1和A2合併爲A4，然後使用相同的算法將A4和A3合併到輸出數組中。

2. 通過反覆比較三個輸入數組中最小的元素並將三個中最小的一個移動到輸出數組，修正上述合併算法。

如果僅考慮數組元素運動（即賦值）的最壞情況，上述兩種算法中的哪一種更有效？

如果僅考慮數組元素比較的最壞情況，上述兩種算法中的哪一種更有效？

在這兩種算法之間，哪一種算法在最壞情況下具有更高的整體效率？

Answer 1

如果您關心的只是陣列寫入次數，第二個版本（三路合併）比第一個算法（雙向合併的兩個實例）快。三路合併算法將完成3n次寫操作（其中n是任何序列的長度），因爲它將一個遍中的所有三個範圍合併在一起。第一種方法是將兩個範圍合併在一起，做2n次寫入，然後將該序列與第三個序列合併，做3n次寫入總共5n次寫入。

更一般地，假設你有k個元素範圍，所有長度爲n。如果兩兩合併這些範圍，然後再次合併這些合併，等等，那麼你將做大致k/2合併步驟合併長度爲n的範圍，然後k/4合併長度爲2n的範圍，然後k/8合併長度4N等，這給出了總和

KN/2 + KN/2 + ... + KN/2（對數n次）

對於爲O陣列寫入的淨數量（KN LG N）。另一方面，如果您在每個步驟中使用k-路比較，那麼您確實需要kn寫入，這比寫小得多。

現在，讓我們考慮一下您在每個設置中做了多少次比較。在三路合併中，寫入輸出序列的每個元素都需要找到三個值中的最小值。這需要兩個比較 - 一個比較前兩個序列的第一個值，一個比較這兩個值的最小值與第三個數組的第一個值。因此，對於寫入結果序列的每個值，我們使用兩個比較，並且由於有3n個值，所以我們最多需要做6n個比較。

更好的方法是將序列存儲在最小堆中，序列通過它們的第一個元素進行比較。在每一步中，我們從堆中的最小第一個值出列序列，將該值寫入結果，然後將序列的其餘部分排入堆中。對於k個序列，這意味着每個寫出的元素至多需要O（lg k）比較，因爲堆插入以O（lg k）運行。這給出了O（kn lg k）的淨運行時間，因爲每個kn元素被寫出需要O（lg k）處理時間。

在另一個版本中，我們開始做一個標準的雙向合併，每個元素要寫一個比較，總共有2n個比較。在合併的第二階段，在最壞的情況下，我們總共進行3n次比較，因爲有3G合併。這給出了總共5n個比較。如果我們使用上面描述的成對合並的廣義構造，我們將需要使用O（kn lg n）比較，因爲每個寫入的元素都需要一個比較，而且我們寫O（kn lg n）。

簡而言之，對於k = 3的具體情況，我們已經知道三路合併對9n個內存讀寫網進行3n次寫和6n次比較。迭代的雙向合併完成了5n個寫操作和5n個比較，總共有10n個內存讀寫，所以三路合併版本更好。

如果我們考慮廣義構造，k路合併對O（nk lg k）個存儲器操作進行O（nk）寫和O（nk lg k）比較。迭代雙向合併算法對O（nk lg n）個存儲器操作進行O（nk lg n）寫入和O（nk lg n）比較。因此，對於一些長序列，k路合併漸近地更好，而對於許多短序列，迭代合併排序更快。

希望這會有所幫助！