C语言演示对归并排序算法的优化实现

归并排序便是建立在这一基础上。归并排序的性能已经很接近比较排序的下界了。timsort的关键特性是极好的利用了数据中存在的规律。如果数据中存在普遍的规律，我们应该尽可能的利用他们，如果没有，我们的算法应该保证不会比普通的归并排序差太多。以上三个问题的答案都是肯定的，并且这也是对归并排序进行优化最为普遍的途径。反复如此直到整个数组有序。考虑下面这种有些奇怪的对普通归并排序工作过程的逆向思考：将整个数组切分成很多长度为1的分区。现在我们有了第一个适应性版本的归并排序：如果数组中有很多有序的子序列，我们就可以走一个很好的捷径。