我决定写这篇文章的主要原因是探索array.prototype.sort（）函数的罩下的内容。 Firefox使用合并排序，而Chrome和Safari则使用Timsort。而且有令人信服的理由选择后者。

谁开发了它

Timsort是由Tim Peters于2002年设计的，主要用于Python编程语言。该算法是如此有效，以至于后来以其他著名的编程语言（例如Java）实施。蒂姆索（Timsort）包括许多实施优化，一些启发式方法和一些精致的调整。它的高级原理很简单：要排序的数组首先贪婪地分解为单调运行（排序子阵列），然后根据特定规则将其成对合并。

与其他分类算法进行比较

Timsort在各种情况下都优于QuickSort和合并。

基本概述

蒂姆索尔特（Timsort）利用了现实世界数据通常部分分类的事实。该算法一次通过数组迭代，以识别已经排序的零件，称为“运行”。这些运行至少应为minRun，我们稍后将解释。

该算法连续检查每个元素，确定它是上升还是下降的一部分。当它遇到一个元素而不是序列的一部分时，它会记录运行并开始新的元素。如果运行的长度小于minRun，则该算法通过添加下一个元素并使用插入排序对数组进行排序来扩展运行。

此循环后，我们有一个由多个运行组成的阵列，每个阵列都与run.length >= minRun。然后将这些排序的运行智能合并。

Timsort是一种稳定的排序算法（保留了相同值的元素顺序），并努力执行平衡合并（合并的合并相似大小）。

插入排序

插入排序是一种简单的方法，可以通过将每个项目逐渐移至正确的位置来对列表进行排序，就像在您的手中安排扑克牌一样。

这是插入的作用：

您可以在这里逐步查看它的工作方式：https://visualgo.net/en/sorting

插入排序与合并排序

插入排序在分类部分排序和小阵列方面表现出色。另一方面，合并排序的目的是尽可能少次将merge()函数调用，更喜欢合并少量的大型分类运行。这就是minRun属性派上用场的地方。最佳运行长度可以平衡插入排序的性能和所需的合并数量。甜点通常位于32至64之间。

微型选择

每个数组的最佳minRun尺寸都会变化。让我们研究蒂姆·彼得斯（Tim Peters）提出的场景。假设我们在数组中有2112个元素，而微型元素为32。前64个运行完美地合并到长度2048的单个运行中。现在，我们有两个长度为2048和64的运行。这需要大量的数据移动才能放置在那64个元素。

解决方案是在这种情况下选择较大的微型，33个更有可能导致64次运行，每个跑步的长度为33。因此，所有合并都是完全平衡的。

运行堆栈

Timsort还采用了巧妙的合并模式。对于随机数据，几乎不可能找到一个超过32个元素的序列。在这种情况下，我们所有的跑步都可能具有相同的长度，并且在合并相等大小的运行时，merge()的性能最佳。但是，连续合并它们可能会导致问题。

想象我们有1000次运行，每32个元素长，除两个元素外，我们还合并了所有元素。我们的运行A长度为999 * 32，并以32的长度运行B。这不是理想的。为了避免此问题，我们检查了堆栈上的最后三个运行（我们将其称为X，Y和Z，其中Z是最近的长度），并检查这些不变性：

• 不变1：z> y + x
• 不变2：y> x

如果两个不变性都正确，则该算法将继续添加运行，直到其中一个失败为止。当发生这种情况时，它将与Z和X的较小键合并Y。直接合并Z和X可以损害稳定性，这确保了分类后具有相同值的元素保持其相对位置。

这种方法实质上确保了最后一次合并的最大运行。

考虑一堆长度[128、64、32、16、8、4、2、2]。蒂姆索（Timsort）将合并最后两个跑步，生产一个长度为4的新跑步，并继续前进，进行完美的合并，就像在2048年游戏中合并正方形一样。

疾驰

通常需要合并不同长度的运行，尤其是当数据部分分类时。为了提高合并速度，蒂姆·彼得斯（Tim Peters）引入了疾驰技术。

通常，merge()函数具有O（m+n）的复杂性，其中m和n表示两个运行的长度。它必须完全循环通过其中一个。

考虑以下情况：我们需要按升顺序合并两个阵列，每个数组包含10,000个元素：

arr1 = [1，2，3 ... 10,000] arr2 = [10,001，10,002，10,003 ... 20,000]

合并运行之前，我们应该比较从ARR1到ARR2 [0]的每个值？取而代之的是，我们可以检测到其中一个阵列始终是“获胜”并触发疾驰。这样我们就可以移动整个跑步部分。

我们该怎么做？我们并没有通过获胜阵列增加1个，而是加倍增量，直到获胜的连胜破裂为止。当这样做时，我们使用二进制搜索来找到新的起点。

在我们的情况下，我们确定在前七个比较之后ARR1赢得了胜利。事实证明，七个比较的连胜纪录是疾驰的最佳触发因素。我们将指针移至1，然后将2、4、8、16等移动。在我们的示例中，获胜的连胜将永远不会结束，因此我们将进行日志（n）比较。

所有红色元素均小于蓝色（这里，21）。因此，它们可以在最终数组中移动到最终数组

但是，如果获胜的条纹结束，我们发现ARR1中最大的值仍然小于ARR2指针下的值，将所有元素推入生成的数组之前，然后从ARR2中的指针重新开始。 /p>

概括

Timsort是巧妙的算法。它结合了来自不同种类的多种技术，并改进了它们。在他的袖子上，它比我在一篇文章中所涵盖的窍门要多。
您可以在此处找到JS实现：https://github.com/lxsmnsyc/TimSort/blob/master/timsort.js

最后，蒂姆索特在行动中：

有用的链接

来源：
Algorithm overview by Tim Peters himself
Wikipedia
Proof of complexity