algorithm - MergeSort 变体的差异？

Question

我正在上一门关于数据结构和算法的大学类(class)，但在使用 MergeSort 时遇到了一些问题。我尝试在网上查看，但结果似乎不一致。

当谈到普通的 MergeSort 和自上而下的 MergeSort - 有什么区别？到目前为止，我所读到的内容使我相信:

“正常”的 MergeSort 只是将一个已经排序的数组/文件分成两半，并将其放入一个辅助数组中。然后我们开始检查辅助数组，方法是连续比较左侧的元素和右侧的元素，将这些元素按排序顺序写入原始数组。

自上而下的 MergeSort 递归地将未排序的数组分成更小的部分，直到我们得到大小为 1 的数组(技术上排序)，直到原始的两半都被排序，然后应用“正常”MergeSort 以获得最终的数组。

我敢肯定我的理解是错误的 - 我在使用 MergeSort 时遇到了很多麻烦。有人可以为我澄清一下吗？

谢谢。

Answer 1

merge sort 的整体思想是使用 divide and conquer 对列表进行排序方法。

规则是您可以比较右侧辅助数组和左侧辅助数组的元素仅 如果它们都已排序。当列表最初未排序时，我们可以保证我们的子数组已排序的唯一方法是当它只有 1 个元素时。此时我们开始 merge 部分，该部分比较左右辅助数组中的元素并将它们排序回主数组。

这是我们合并排序时发生的事情的示例:

如您所见，我们只是将数组减半，直到我们得到一个有保证的排序数组(只有 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