合并排序在最坏情况下如何具有空间复杂度O（n）？
O（n）复杂度意味着在最坏的情况下合并排序需要的存储空间等于初始数组中存在的元素数量。 但是，它没有创建新的数组，同时进行递归调用？ 如何计算这个空间？
如果在对递归调用自身进行递归调用之前，它在mergesort（）中分配了数组的两半部分，则最差情况下自顶向下合并排序的实现可能会占用比原始数组更多的空间。
更高效的自顶向下合并排序使用一个入口函数执行临时缓冲区的一次分配，将临时缓冲区的地址作为参数传递给一对相互递归函数中的一个，这些函数生成索引并在两个数组之间合并数据。
在自底向上合并排序的情况下，可以使用临时数组1/2的原始数组大小，合并数组的两半，结束于临时数组中的前半部分数据，而后半部分在原始数组中，然后进行最后的合并回原始数组。
然而，无论哪种情况，空间复杂度都是O（n），因为对于大O而言，像2或1/2这样的常量被忽略。
MergeSort具有与原始数组大小相同的单个缓冲区。
在通常的版本中，您将执行从数组到另一个缓冲区的合并并将其复制回数组。
在高级版本中，您可以执行从数组到另一个缓冲区的合并，反之亦然。
注意：这个回答是错误的，正如我在评论中指出的那样。 我将它留在这里，因为我相信这对大多数想要了解这些事情的人有帮助，但请记住，该算法实际上称为in-place mergesort，并且可能具有与纯mergesort不同的运行时复杂性。
合并排序很容易实现，为所有内容使用相同的数组，而无需创建新的数组。 只需在每次递归调用中发送界限即可。 所以像这样（伪代码）：
mergesort(array) ->
mergesort'(array, 0, length of array - 1)
mergesort'(array, start, end) ->
mergesort'(array, start, end/2)
mergesort'(array, end/2+1, end)
merge(array, start, end/2, end/2+1, end)
merge(array, start1, end1, start2, end2) ->
// This function merges the two partitions
// by just moving elements inside array
上一篇: How does merge sort have space complexity O(n) for worst case?