快速排序与就地合并排序

就地合并排序的常见实现是递归的,快速排序是递归的,或者两者都使用某种形式的堆栈,因此使用堆栈空间,o(log2(n))表示合并排序,快速排序也可以限制为o(log2(n)),只在分区步骤后的较小部分使用递归,并在较大部分使用循环,但时间复杂度仍然可能是o(n^2)最坏的情况。

常见的就地合并排序速度较慢,也不稳定。有一些版本的merge sort已经就位并且稳定,但是速度很慢。

通用就地合并排序的算法是对数组的后半部分和第一部分进行排序,而不排序数组的第二部分。然后从第二季度开始,第一季度和第二季度合并到数组中。每次合并一个元素,而不是移动它时,该元素都会被交换,因此在合并步骤中,第二季度的未排序数据会分散在已排序部分周围(这就是为什么该算法不“稳定”)。合并步骤完成后,所有无序元素都将在第一季度结束,其余的数组将被排序。接下来,对数组的前八分之一进行排序,然后将前八分之一和最后三个四分之一合并到数组的第二个八分之一中,使第一个八分之一包含未排序的数据,并对数组的其余部分进行排序。此过程将继续,直到数组左侧只有两个未排序的元素。这两个元素使用插入排序移动到位。

注意,这不是一个稳定的类型。

更新-块合并排序是稳定的,并且具有时间复杂性o(n log(n)),但具有较低的顺序因子,这使得它比使用第二个缓冲区的普通合并排序慢。如果至少有2··sqrt(n)个唯一值,那么它的工作效果最好,这允许它们重新排序以提供数组的工作区域并保持稳定。

https://en.wikipedia.org/wiki/Block_sort