[译]理解timsort, 第一部分:适应性归并排序(Adaptive Mergesort)

Python2.3中开始使用的timsort应该说算是声名在外了,不管是在稳定性还是在速度上都十分的惊人。
前一段刚刚看了《Python CookBook》中的一些章节,对timsort产生了一些兴趣。于是在网上看到了这边文章,讲的相当清楚明了,于是产生了翻译的念头,也于是有了这篇文章。

这应该算是我翻译的第一篇技术文章,真正做一次才明白能看懂和能翻译出来还是有蛮大的差距的。翻译质量不可谓不差,诸位如果英文阅读无障碍,强烈建议移步原文:Understanding timsort, Part 1: Adaptive Mergesort,如果你不幸看了下面的坑爹译文,欢迎留下各种吐槽!闲话少说,上主菜:


Python的timsort常常被认为是很复杂、可怕的。这是可以理解的,因为其中包含了太多的细节。但是,如果你真正的了解它,你会发现它其实只是对归并排序进行了一系列的改进。其中有一些是很聪明的,而也有一些是相当简单直接的。这些大大小小的改进聚集起来使得算法的效率变得十分的吸引人。

我将会通过一些例子告诉你如何从一个最基本的归并排序开始逐步得到timsort。在本文中我会讲述如何得到timsort的“核心”:基本的适应性归并排序。后续的文章会在此基础上讲述timsort中使用的其他特别的优化。
继续阅读: