前面讲的还没有涉及到排序算法的核心部分。即有没有办法改进合并算法呢？

合并两个排号序列需要额外的等长空间。如果不额外申请空间，就只能用O(n2)至O(nlogn)的方法代替。但是这个问题真的就有那么难吗？

事实上这是一系列看似十分简单但真要解决起来难死无数人的问题之一。

改进算法该从哪个方向着手？

先来看一下，所有的计算机算法，都可以用五个维度来衡量质量，他们是：

• 空间
• 时间
• 稳定度
• 精确度
• 数据特殊性

基本上，可以降低一个方向上的标准来获得其他四项方面的提升。那些广泛流传，使用普遍的算法无不是在各个方面都取得了较为完美的平衡。有些算法在某几个维度上比较极端，适合用来处理特殊情况。而剩下的其他算法基本上不具有实用价值。

在一般工程上算法的设计，其实就是在平衡这五个项目，这里面包含了平时工作中用到的所有指导原则：

空间：如果允许使用额外的空间，常常能把时间复杂度降到比n更低，甚至1，比如查表法，基数排序法等。

时间：如果空间使用受限，就很可能要接受时间上提高复杂度，最终可能得不偿失。比如尝试解决合并有序数列不额外耗费空间的问题.

基本上算法复杂度 = 空间复杂度x时间复杂度

稳定度：如果愿意牺牲算法的稳定度，或许能够在时间和空间上获得巨大的利益，比如快排就是用不稳定算法替换掉了O(N)的空间消耗，从而成为目前排序算法中的王者。

精确度：一般我们都要求计算机的运算结果100%精确，但如果允许计算结果哪怕牺牲掉一丁点儿的精确度，就能期待在空间和时间上获得极大的提升。降低精确度，在不要求获得真正精确的数据的场合特别有用，比如web搜索，近年来由于云服务，云数据的概念炒热，相关的算法也逐渐进入大家的视野。不过允许非100%精确度的使用场合还是非常之少的。

数据特殊性：有一些比O(nlogn)更低的排序算法被开发出来，但都是基于特定的数据类型，或满足特定条件的数据集合等。在日常工作中，这是个很有用的技巧，因为绝大部分时候我们都只需要处理特定的数据类型和数据集合，因此，选择应付特殊性的算法可以节省大量的时间空间成本，比如前一篇文章中，将求最高位数的问题，转成求最高位的奇偶性的问题，问题的解法直接从O(n)降到O(1)。

再来看我们想要改进的算法，精确度肯定是不能损失，泛用的算法数据也不能有特殊性，在算法复杂度不会低于O(NlogN)的情况下，突破的方向看来就只剩下降低稳定度一条路可走了——而这正是快速排序做的事——用一个不稳定但是十分绝妙的交换顺序算法代替了O(n)的空间消耗，从而摘走了排序算法的桂冠，甚至还成为了上世纪最伟大的计算机算法之一。想象一下，一个耗费O(n)空间的快排算法其实还不如归并算法。

所以归并算法想要有所突破，就需要像快速排序那样找个替换空间的不稳定算法出来，如果能找到的话，至少能和快排平分秋色吧。

结果，还真有人宣称找到了改进的方法：

在这个链接的论文里，作者宣称找到了合并有序数列，在线性时间，不耗费额外的On空间，但是不稳定的算法。这个算法知道的人不多，但看样子是相当复杂吧，就算是On的算法，实施起来过于麻烦的话，大概大家还是去用快排算法了。