除了冒泡排序，你知道Python内建的排序算法吗？

对于编程算法，可能很多读者在学校第一个了解的就是冒泡排序，但是你真的知道 Python 内建排序算法 list.sort() 的原理吗?它使用的是一种快速、稳定的排序算法 Timsort，其时间复杂度为 O(n log n)，该算法的目标在于处理大规模真实数据。

Timsort 是一种对真实数据非常有效的排序算法。Tim Peters 在 2001 年为 Python 编程语言创造了 Timsort。Timsort 首先分析它要排序的列表，然后基于该分析选择合理方案。

Timsort 自发明以来，就成为 Python、Java 、Android 平台和 GNU Octave 的默认排序算法。

图源：

Timsort 的排序时间与 Mergesort 相近，快于其他大多数排序算法。Timsort 实际上借鉴了插入排序和归并排序的方法，后文将详细介绍它的具体过程。

Peters 设计 Timsort 是为了利用大量存在于现实数据集中的有序元素，这些有序元素被称为「natural runs」。总而言之，Timsort 会先遍历所有数据并找到数据中已经排好序的分区，且每一个分区可以称为一个 run，最后再按规则将这些 run 归并为一个。

数组中元素少于 64 个

如果排序的数组中元素少于 64 个，那么 Timsort 将执行插入排序。插入排序是对小型列表最有效的简单排序，它在大型列表中速度很慢，但是在小型列表中速度很快。插入排序的思路如下：

逐个查看元素

通过在正确的位置插入元素来建立排序列表

下面的跟踪表说明了插入排序如何对列表 [34, 10, 64, 51, 32, 21] 进行排序的：

在这个示例中，我们将从左向右开始排序，其中黑体数字表示新的已排序子数组。在原数组每一个元素的排序中，它会从右到左对比已排序子数组，并插入适当的位置。用动图来说明插入排序：

天然有序的区块：run

如果列表大于 64 个元素，则 Timsort 算法首先遍历列表，查找「严格」升序或降序的部分(Run)。如果一个部分递减，Timsort 将逆转这个部分。因此，如果 run 递减，则如下图所示(run 用粗体表示)：

如果没有递减，则如下图所示：

minrun 的大小是根据数组大小确定的。Timsort 算法选择它是为了使随机数组中的大部分 run 变成 minrun。当 run N 的长度等于或略小于 2 的倍数时，归并 2 个数组更加高效。Timsort 选择 minrun 是为了确保 minrun 等于或稍微小于 2 的倍数。

该算法选择 minrun 的范围为 32 ~ 64。当除以 minrun 时，使原始数组的长度等于或略小于 2 的倍数。

如果 run 的长度小于 minrun，则计算 minrun 减去 run 的长度。我们可以将 run 之外的新元素(minrun - run 个)放到 run 的后面，并执行插入排序来创建新的 run，这个新的 run 长度和 minrun 相同。

如果 minrun 是 63，而 run 的长度是 33，那么可以获取 63 - 33 = 30 个新元素。然后将这 30 个新元素放到 run 的末尾并作为新的元素，所以 run 的第 34 个元素 run[33] 有 30 个子元素。最后只需要对后面 30 个元素执行一个插入排序就能创建一个长度为 63 的新 run。

在这一部分完成之后，现在应该在一个列表中有一系列已排序的 run。

归并

Timsort 现在需要执行归并排序来合并 run，需要确保在归并排序的同时保持稳定和平衡。为了保持稳定，两个等值的元素不应该交换，这不仅保持了它们在列表中的原始位置，而且使算法更快。

当 Timsort 搜索到 runs 时，它们会被添加到堆栈中。一个简单的堆栈是这样的：

想象一堆盘子。你不能从底部取盘子，必须从顶部取，堆栈也是如此。

当归并不同的 run 时，Timsort 试图平衡两个相互矛盾的需求。一方面，我们希望尽可能地延迟归并，以便利用之后可能出现的模式。但我们更希望尽快归并，以利用刚才发现的在内存层级中仍然排名很高的 run。我们也不能「过分」延迟合并，因为它记住未合并的运行需要消耗内存，而堆栈的大小是固定的。

为了得到折衷方案，Timsort 追踪堆栈上最近的三个项，并为这些堆栈项创建了两个必须保持为 True 的规则：

A > B + C

B > C

其中 A、B 和 C 是堆栈中最近的三个项。