最近本人想出了一个排序算法，叫“快速归并排序”即快速排序和归并排序的结合。有点耗空间

名称	快速归并排序
时间复杂度	O(nlogn)
最好情况	O（nlogn）
最差情况	O（nlogn）
空间复杂度	O（n）
稳定性	不稳定
它改进了快速排序，快速排序经常把元素分为长度不相近的两个序列，快速归并排序则不会出现这种情况。

排序思路

1.首先排序前半部分；

2.用前半部分的中间一项为基准数，对后半部分进行一趟快速排序；

3.递归排序分区后的后半部分的两个区；

4.最后，归并两个排好序的序列。

在第二步时，大概率都会选择出一个比较“好”的基准数，最差情况也只会把元素分为3：1 的两个序列，在这种情况下，时间复杂度也还是O（nlogn）。（请自己想一想为什么时间复杂度也还是O（nlogn））

排序用时

当元素个数为10000000，电脑开最佳性能时，用时如下。

类型	时间（秒）
无序（第一次）	2.64
无序（第二次）	2.791
无序（第三次）	3.133
倒序（第一次）	3.926
倒序（第二次）	2.62
倒序（第三次）	3.17
可以看到的，元素倒序时，对性能的影响不大。

复杂度和稳定性分析

时间复杂度

首先，快速归并排序要排序前半部分。然后，花0.5n的时间对右边进行一趟快速排序，再递归排序分出的两个区，最后花1.5n的时间合并它们，即有：

O（n）=O(n/2)+2*o(n/4)+2n

即O（nlogn）。

空间复杂度

合并两个序列的空间复杂度本来就是O（n），该算法的空间复杂度为O（n）。

稳定性

快速排序本来就不稳定，所以该算法不稳定。

变体

你应该注意到了，不一定每次进行一趟快速排序都要先构建一个有序序列。比如，第一次用前半部分的正中间为基准数，第二次就用前半部分的前半部分的（指前半部分的1/4处）正中间为基准数，第三次就用前半部分的前半部分的前半部分的（指前半部分的1/8处）正中间为基准数，以此类推，只需要构建logn次有序序列。这样，在进行快速排序时，就会遍历完整个左半部分。不妨在这时就把前半部分复制到额外空间里，后期合并时就不用再复制一遍了。

用这种方法效率确实更高，但最差情况时间复杂度会退化成平方级。

尾声

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