如果你没看过上回我发布的帖子，请先看一下。

请先看一下

我仔细想了想，该算法其实不一定必须非原地。

不知道大家有没有学过单轴的快速排序，如果学过，请跳过这一段。

单轴快速排序

单轴快速排序是快速排序的一种。 举个例子，有一个待排序的序列为[5,8,0,1,3,9,8,2,4,6],那么单轴快速排序是这样排的:

首先选取第一项为基准数,然后使用两个指针，这里就称为 左=1，右=2 ；首先比较 第[右]项 和基准数，不比基准数小就不用管，这里8>5，所以不用管。然后 右++，现在0<5 ! ,看来要处理一下了。将 第[右]项 和 第[左]项 交换就好了。可是现在基准数5被移动到最后面了，所以还需要再将基准数交换回去。现在序列变成这样： [0,5,8,1,3,9,8,2,4,6]

然后继续 右++，但此时 左 也要++。（请自己想一想为什么） 就这样不断地找比基准数小的数，然后与“左”交换，再将基准数与（左+1）交换，直到 右 大于n。 此时完成一次分区的序列：[0,1,3,2,4,5,8,8,9,6] 然后再向两边递归排序即可。

In-plase的梦

那么快速归并排序也可以这样做。

0.如果元素只有两个，比较它们，顺序错误就交换。

1.首先排序后半部分；

2.选后半部分的正中间为基准数，进行单轴快速排序。

3.继续将分区分出的后半部分滚动到右边有序序列中，使其到基准数后面。

4.递归排序两部分。

注意，每次分治后，一段无序序列旁总有一段有序序列供它选取基准数，所以这个算法的优化甚至比优化前的变体还要快！

尾声

如果你对这个算法有意见，请到评论区说。