我正在学习数据结构和算法的大学类(class)，但在合并排序方面遇到了一些问题。我尝试在网上查看，但结果似乎不一致。
当谈到普通的合并排序和自上而下的合并排序时，有什么区别？到目前为止我所读到的内容让我相信:
“普通”MergeSort 只是将已排序的数组/文件分成两半并将其放入辅助数组中。然后我们开始检查辅助数组，连续比较左侧的元素与右侧的元素，将这些元素按排序顺序写入到原始数组中。
自上而下的归并排序会递归地将未排序的数组分成更小的部分，直到我们得到大小为 1 的数组(技术上已排序)，直到原始的两半数组都已排序，然后应用“正常”归并排序以获得最终的数组数组。
我确信我的理解是错误的 - 我在合并排序方面遇到了很多麻烦。有人可以帮我澄清一下吗？
谢谢。
最佳答案
合并排序的整体思想是使用divide and conquer对列表进行排序。方法。
规则是，只有当右侧辅助数组和左侧辅助数组都已排序时，您才能将它们进行比较。当列表最初未排序时，我们可以保证子数组已排序的唯一方法是当它只有 1 个元素时。此时，我们开始合并部分，该部分比较左右辅助数组中的元素并将它们重新排序到主数组中。
下面是我们合并排序时发生的情况的示例:
正如你所看到的，我们只是将数组减半，直到得到一个有保证的排序数组(只有 1 个元素)，现在我们可以将子数组合并在一起，因为它们已经排序了。
如果您想了解更多相关信息，这里有一些很好的资料，但在我看来，您从概念上已经掌握了合并排序的用途，您可能只是有一些这些技术有点困惑。
关于algorithm - 归并排序的变体有何差异？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35201963/