Python 的 timsort 算法出了名的晦涩难懂。这是情理之中的事，它非常复杂。不过，当你真正对它进行深入研究后，你会发现它“只不过”是归并排序的一个变种。这些变异，有的非常巧妙，有的则非常直接明了，总之令人印象颇为深刻。
我会通过一些例子，让你从基本的归并算法（mergesort）开始，逐步过渡到 timsort。在本文中，我将探讨如何实现基本的自适应归并排序算法（adaptive mergesort），该算法是 timsort 的核心。以后的文章会在此基础上，讨论timsort中更多具体的优化。
为了简单起见，我不打算考虑普遍情况，只考虑整型数组（很容易类推到其他类型， 也使得代码更容易理解）。需要说明的是，我将隐藏一些细节（可能会有一些不太严谨的地方）。所以，如果你希望了解算法的具体细节，还是应该参考Tim Peters的说明。
对了，例子是 C 写的，Sorry。
那么，我们从最简单的归并算法开始吧。
假定你已经了解归并算法的原理（如果不知道的话，你就得问下度娘）。一起复习下：长度为1的数组是有序的；当数组长度n > 1，则将数组拆分为2部分（通常从数组中间拆分）；分别对两部分进行归并排序；然后执行一次合并操作，遍历两个有序数组，依次将较小的元素插入结果数组，最终得到一个较大的有序数组。
上代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include "timsort.h" #include <stdlib.h> #include <string.h> //p1、p2分别为长l1, l2的有序数组，将它们合并到 //一个target数组，target可能与p1、p2有重叠， //但target必须有足够的空间保存整个合并后的数组。 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数组，如果 //有两个相等元素，为了保持稳定性，我们写入靠前的元素。 //这对int数据当然没所谓，领会精神就行 :)。 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++; } //如果任意一个数组排序完成，我们将另一个数组剩余的 //数据全部直接copy到结果数组。 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); } |
我没有贴出完整的代码，你可以在github中查看详情。
到了这一步，如果你是C程序员，可能有件让你非常心惊肉跳的事摆在你眼前：每次调用合并函数的时候，都频繁的申请、释放用于合并操作的内存（我们没检查null返回值，这可能也让你很纠结。除非在demo版中，我会在生产代码中检查返回值的，但愿这能让你宽心）。
我们只要稍稍修改一下原型，再封装一下就可以解决这个问题。
|
1 2 3 4 5 6 7 8 |
void merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]); tanding-timsort-1adaptive-mergesort/">David R. MacIver。欢迎加入翻译组。 Python 的 timsort 算法出了名的晦涩难懂。这是情理之中的事，它非常复杂。不过，当你真正对它进行深入研究后，你会发现它“只不过”是归并排序的一个变种。这些变异，有的非常巧妙，有的则非常直接明了，总之令人印象颇为深刻。 我会通过一些例子，让你从基本的归并算法（mergesort）开始，逐步过渡到 timsort。在本文中，我将探讨如何实现基本的自适应归并排序算法（adaptive mergesort），该算法是 timsort 的核心。以后的文章会在此基础上，讨论timsort中更多具体的优化。 为了简单起见，我不打算考虑普遍情况，只考虑整型数组（很容易类推到其他类型， 也使得代码更容易理解）。需要说明的是，我将隐藏一些细节（可能会有一些不太严谨的地方）。所以，如果你希望了解算法的具体细节，还是应该参考Tim Peters的说明。 对了，例子是 C 写的，Sorry。 那么，我们从最简单的归并算法开始吧。 假定你已经了解归并算法的原理（如果不知道的话，你就得问下度娘）。一起复习下：长度为1的数组是有序的；当数组长度n > 1，则将数组拆分为2部分（通常从数组中间拆分）；分别对两部分进行归并排序；然后执行一次合并操作，遍历两个有序数组，依次将较小的元素插入结果数组，最终得到一个较大的有序数组。 上代码：
我没有贴出完整的代码，你可以在github中查看详情。 到了这一步，如果你是C程序员，可能有件让你非常心惊肉跳的事摆在你眼前：每次调用合并函数的时候，都频繁的申请、释放用于合并操作的内存（我们没检查null返回值，这可能也让你很纠结。除非在demo版中，我会在生产代码中检查返回值的，但愿这能让你宽心）。 我们只要稍稍修改一下原型，再封装一下就可以解决这个问题。
现在我们得到一个封装的排序函数，在函数内完成初始化，然后进行递归调用。在timsort中，我们会经常用到这种模式。但是传入工作函数的内存，最终会比直接使用一整块内存块的情况复杂的多。 我们终于得到了一个基本的归并排序。我们得想想：如何优化？ 一般来说，我们不可能找到一种万能的优化方案。归并排序的性能非常接近最优化的比较排序（comparison sort）。timsort最关键特性是，它能充分利用数据中的某些共同规律。如果存这种规律，我们就要充分利用。否则，我们只要达到和普通归并排序基本一样的效率就可以了。 |
