基础
如果有两个数组已经有序，那么可以把这两个数组归并为更大的一个有序数组。归并排序便是建立在这一基础上。要将一个数组排序，可以将它划分为两个子数组分别排序，然后将结果归并，使得整体有序。子数组的排序同样采用这样的方法排序，这个过程是递归的。
下面是示例代码：
#include "timsort.h"
#include <stdlib.h>
#include <string.h>
// 将两个长度分别为l1, l2的已排序数组p1, p2合并为一个
// 已排序的目标数组。
void merge(int target[], int p1[], int l1, int p2[], int l2);
void integer_timsort(int array[], int size){
if(size <= 1) return;
int partition = size/2;
integer_timsort(array, partition);
integer_timsort(array + partition, size - partition);
merge(array, array, partition, array + partition, size - partition);
}
void merge(int target[], int p1[], int l1, int p2[], int l2){
int *merge_to = malloc(sizeof(int) * (l1 + l2));
// 当前扫描两数组的位置
int i1, i2;
i1 = i2 = 0;
// 在合并过程中存放下一个元素的位置
int *next_merge_element = merge_to;
// 扫描两数组，将较小的元素写入
// merge_to. 当两数相等时我们选择
// 左边的, 因为我们想保证排序的稳定性
// 当然对于integers这无关紧要，但这种想法是很重要的
while(i1 < l1 && i2 < l2){
if(p1[i1] <= p2[i2]){
*next_merge_element = p1[i1];
i1++;
} else {
*next_merge_element = p2[i2];
i2++;
}
next_merge_element++;
}
// 如果有一个数组没有扫描完，我们直接拷贝剩余的部分
memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1));
memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2));
// 现在我们已经将他们合并在了我们的额外的存储空间里了
// 是时候转存到target了
memcpy(target, merge_to, sizeof(int) * (l1 + l2));
free(merge_to);
}
</div>
#include "timsort.h"
#include <stdlib.h>
#include <string.h>
// 将两个长度分别为l1, l2的已排序数组p1, p2合并为一个
// 已排序的目标数组。
void merge(int target[], int p1[], int l1, int p2[], int l2);
void integer_timsort(int array[], int size){
if(size <= 1) return;
int partition = size/2;
integer_timsort(array, partition);
integer_timsort(array + partition, size - partition);
merge(array, array, partition, array + partition, size - partition);
}
void merge(int target[], int p1[], int l1, int p2[], int l2){
int *merge_to = malloc(sizeof(int) * (l1 + l2));
// 当前扫描两数组的位置
int i1, i2;
i1 = i2 = 0;
// 在合并过程中存放下一个元素的位置
int *next_merge_element = merge_to;
// 扫描两数组，将较小的元素写入
// merge_to. 当两数相等时我们选择
// 左边的, 因为我们想保证排序的稳定性
// 当然对于integers这无关紧要，但这种想法是很重要的
while(i1 < l1 && i2 < l2){
if(p1[i1] <= p2[i2]){
*next_merge_element = p1[i1];
i1++;
} else {
*next_merge_element = p2[i2];
i2++;
}
next_merge_element++;
}
// 如果有一个数组没有扫描完，我们直接拷贝剩余的部分
memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1));
memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2));
// 现在我们已经将他们合并在了我们的额外的存储空间里了
// 是时候转存到target了
memcpy(target, merge_to, sizeof(int) * (l1 + l2));
free(merge_to);
}
</div>
我不会总是贴出完整的代码~
优化
现在，如果你是一个C程序员，你可能已经在吐槽了：我在每次合并过程中都申请并释放了一次额外存储空间（你可能也会不爽于我没有检查返回值是否为null,请无视之…如果这能让你感觉好一点）
这个问题只要一点点的改动就可以修正：
void merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]);
void integer_timsort_with_storage(int array[], int size, int storage[]);
void integer_timsort(int array[], int size){
int *storage = malloc(sizeof(int) * size);
integer_timsort_with_storage(array, size, storage);
free(storage);
}
void merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]);
void integer_timsort_with_storage(int array[], int size, int storage[]);
void integer_timsort(int array[], int size){
int *storage = malloc(sizeof(int) * size);
integer_timsort_with_storage(array, size, storage);
free(storage);
}
</div>
现在我们有了排序函数的最顶层，做了一些内存分配（setup）工作并将其传入调用中。这是我们将要开始优化工作的模版，当然最后实际可用的版本会更加复杂而不仅仅是优化一块内存空间。
现在我们有了基本的归并排序了，我们需要想想：我们能怎样来优化它？
一般来说我们不能指望对于每一种情况都能达到最优。归并排序的性能已经很接近比较排序的下界了。timsort的关键特性是极好的利用了数据中存在的规律。如果数据中存在普遍的规律，我们应该尽可能的利用他们，如果没有，我们的算法应该保证不会比普通的归并排序差太多。
如果你看过归并排序的实现，你会发现其实所有的工作都是在合并（merge）的过程当中完成的。所以优化的重点也就落在了这里。由此我们得出以下三点可能的优化途径：
1、能否使合并过程运行的更快？
2、能否执行更少的合并过程？
3、是否存在一些与其使用归并排序不如使用其他排序的情况？
以上三个问题的答案都是肯定的，并且这也是对归并排序进行优化最为普遍的途径。举例来说，递归的实现使得根据数组的规模使用不同的排序算法变的非常简单。归并排序是一个很好的通用性排序算法，（具有很好的渐进复杂度）但对小数组而言常数因子就显得愈发重要，当数组的大小小于某个值时（通常是7或者8左右）归并排序的性能频繁的低于插入排序。
这并不是timsort的原理，但是我们之后会用到插入排序，所以我们先开个小差。
最简单的：假设我们有一个具有n个元素的已排序数组，并且在尾端有第n+1个元素的位置。现在我们想要向里面添加一个新的元素并保持数组有序。我们需要为新元素找到一个合适的位置并将比它大的数向后移动。一种显而易见的做法是将新元素放到第n+1个位置上，然后从后向前两两交换直到到达正确的位置（对较大的数组这并不是最好的做法：你可能想要对数据进行二分查找（binary search）然后把剩下的元素不做比较的向后移动。但是对小数组来说这样的做法反而不是很好，due to cache effects）
这就是插入排序工作的方式：当你有了k个已排序的元素，将第k+1个元素插入其中，你就有了k+1个已排序的元素。反复如此直到整个数组有序。
下面是代码：
void insertion_sort(int xs[], int length){
if(length <= 1) return;
int i;
for(i = 1; i < length; i++){
// i之前的数组已经有序了，现在将xs[i]插入到里面
int x = xs[i];
int j = i - 1;
// 将j向前移动直到数组头或者
// something <= x, 并且其右边的所有的元素都已经
// 右移了
while(j >= 0 && xs[j] > x){
xs[j+1], xs[j];
j--;
}
xs[j+1] = x;
}
}
</div>
void insertion_sort(int xs[], int length){
if(length <= 1) return;
int i;
for(i = 1; i < length; i++){
// i之前的数组已经有序了，现在将xs[i]插入到里面
int x = xs[i];
int j = i - 1;
// 将j向前移动直到数组头或者
// something <= x, 并且其右边的所有的元素都已经
// 右移了
while(j >= 0 && xs[j] > x){
xs[j+1], xs[j];
j--;
}
xs[j+1] = x;
}
}
</div>
现在排序的代码会被修改为下面这样：
void integer_timsort_with_storage(int array[], int size, int storage[]){
if(size <= INSERTION_SORT_SIZE){
insertion_sort(array, size);
return;
}
}
</div>
void integer_timsort_with_storage(int array[], int size, int storage[]){
if(size <= INSERTION_SORT_SIZE){
insertion_sort(array, size);
return;
}
}
</div>
你可以在这里查看这个版本