MergeSort變體的差異？

Question

我正在參加數據結構的大學課程&算法，並在MergeSort中遇到了一些麻煩。我試圖在網上看，但結果似乎不一致。

當談到正常的MergeSort和自頂向下的MergeSort時，有什麼區別？到目前爲止，我讀過的東西讓我相信：

「普通」MergeSort只是將已排序的數組/文件拆分爲一半，並將其放入輔助數組中。然後我們開始通過連續比較左邊的元素和右邊的元素來檢查輔助數組，將這些元素寫入排序順序，回到原始數組中。

一個自頂向下的MergeSort遞歸地將一個未排序的數組分割成更小的部分，直到我們得到一個大小爲1的數組（直到排序後），然後使用「普通」MergeSort獲得最終陣列。

我很積極，我的理解是錯誤的 - 我有很多MergeSort的麻煩。有人能爲我澄清這件事嗎？

謝謝。

Answer 1

merge sort的整個想法是使用divide and conquer方法對列表進行排序。

規則是你可以比較右輔助數組的元素與左輔助數組只有如果他們都被排序。當列表最初未排序時，我們可以保證我們的子數組排序的唯一方法是隻有一個元素。在這一點上，我們開始merge部分，它比較來自左和右輔助數組的元素並將它們分類回主數組。

這裏是發生了什麼事，我們當merge sort的例子：

正如你所看到的，我們只是在陣列的一半，直到我們得到了一個保證有序數組（僅1元），現在我們可以將子陣列數組合並在一起，因爲它們是排序的。

這裏有一些很好的資料來源，如果你想了解更多關於它的信息，但在我看來，你在概念上已經掌握了merge sort應該做的事情，你可能會混淆一些技巧。

• https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort
• https://en.wikipedia.org/wiki/Merge_sort
• http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html

Answer 2

歸併的最流行的變化是自上而下尼克朱伯中詳細地描述。

自下而上的變體不會將整個陣列分成越來越小的部分。相反，它
在第一級合併長度1
陣列在第二階段，在第三階段合併長度2
的陣列，直到達到全長合併長度4個
ANS等的陣列。

從第四行到最後考慮Nick的方案 - 他們是自下而上的階段。