Time Sort

Timsort: A very fast , O(n log n), stable sorting algorithm built for the real world — not constructed in academia.

算法简介

Timsort 是一种对真实数据有效的排序算法，而不是在学术实验室中创建的。

Tim Peters在2001年为Python编程语言创建了Timsort。Timsort首先分析它要排序的列表，然后根据列表的分析选择一种方法。

自从该算法被发明以来，它在Python、Java、Android平台和GNU Octave中被用作默认的排序算法。

Timsort的大O符号是O(n log n)，为了学习大O符号，请阅读它。

具体

Timsort的排序时间与 Mergesort(归并排序) 一样，比大多数其他类型的排序都要快。

Timsort 实际上使用了插入排序和归并排序，您很快就会看到。

Peters设计了Timsort以使用在大多数现实世界的数据集中存在的已经有序的元素。

它将这些已经有序的元素称为“自然运行”。它迭代数据，将元素收集到运行中，并同时将这些运行合并到一个运行中。

插入元素低于 64 个

如果我们要排序的数组中元素少于64个，Timsort将执行插入排序。

插入排序是对小列表最有效的简单排序。在更大的列表中，它的速度很慢，但在小列表中却非常快。

插入排序的概念如下:

  • 逐个查看元素

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

例子

  • 待排序数组

[34, 10, 64, 51, 32, 21]

  • 具体排序过程
[34, 10, 64, 51, 32, 21]
[10, 34, 64, 51, 32, 21]
[10, 34, 51, 64, 32, 21]
[10, 34, 51, 64, 32, 21]
[10, 32, 34, 51, 64, 21]
[10, 21, 32, 34, 51, 64]

排序元素超过 64 个

如果列表大于64个元素，算法将首先遍历列表，查找严格递增或递减的部分。

如果这个部分是递减的，它就会反转这个部分。

  • 递减

所以如果运行是递减的，它会是这样的(运行在粗体中):

[3, 2, 1, 9, 17, 34]
[1, 2, 3, 9, 17, 34]
  • 非递减
[2, 3, 4, 17, 94]
[2, 3, 4, 17, 94]

ps: 图示主要指数组前 3 个元素(严格递增或递减的部分)？

minrun 是根据数组的大小确定的大小。

算法选择它，以便在一个随机数组中大多数运行的长度是或变成minrun。当运行次数等于或略小于2次幂时，合并2个数组会更有效。

Timsort选择minrun以确保这种效率，方法是确保minrun等于或小于2的幂。

算法选择minrun范围为32到64(含)。它选择minrun，使原始数组的长度除以minrun，等于或略小于2的幂。

如果运行的长度小于minrun，则计算从minrun运行的长度。使用这个新数字，您可以在运行之前获取许多项，并执行插入排序以创建新的运行。

如果minrun是63，运行的长度是33，那么 63 - 33 = 30。

然后从运行结束前获取30个元素，这是来自运行[33]的30个项目，然后执行插入排序以创建新的运行。

在这部分完成之后，我们现在应该有一堆排序的运行在列表中。

Merge (归并)

Timsort现在执行归并排序来合并运行。但是，Timsort确保在合并排序时保持稳定和合并平衡。

为了保持稳定，我们不应该交换两个相等的数值。这不仅保持了它们在列表中的原始位置，而且使算法更快。我们将很快讨论合并平衡。

当Timsort发现运行时，它将它们添加到堆栈中。一个简单的堆栈是这样的:

a

b

c

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

Timsort试图在归并排序运行时平衡两个相互竞争的需求。

一方面，我们希望尽可能地推迟合并，以便利用稍后可能出现的模式。

但我们更希望尽快进行合并，以利用刚才发现的运行仍然在内存层次结构中较高的运行。

我们也不能延迟合并“太长”，因为它消耗内存来记住仍然没有合并的运行，并且堆栈有一个固定的大小。

为了确保我们有这个妥协，Timsort跟踪栈上最近的三个项目，并创建两个必须符合这些项目的规则:

  1. A > B+C

  2. B > C

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

What turned out to be a good compromise maintains two invariants on the stack entries, where A, B and C are the lengths of the three righmost not-yet merged slices. —— by Tim Peters

通常，合并不同长度的相邻运行是很困难的。更困难的是我们必须保持稳定。

为了解决这个问题，Timsort将临时内存放在一边。它将两个运行中的较小的(同时调用运行A和B)放入临时内存中。

Galloping (飞驰的)

当Timsort正在合并A和B时，它注意到一个运行已经连续多次“获胜”。

如果运行A由比运行B小得多的数组成，那么运行A会回到原来的位置。合并这两个运行将需要大量的工作来实现什么。

通常情况下，数据会有一些预先存在的内部结构。Timsort假设如果很多运行a的值都低于运行B的值，那么很可能a的值会继续小于B。

A = [1,2,3,4]
B = [5,6,7,8]

Timsort然后将进入快速模式。Timsort不是检查 [0] 和 b[0]， 而是对 [0] 中 b[0] 的适当位置进行二分查找(binary search)。

这样，Timsort就可以将a的整个部分移动到合适的位置。

然后Timsort在B中搜索 [0] 的适当位置，Timsort就会同时移动 B 的整个部分，并将其放到合适的位置。

让我们来看看这个。Timsort检查 B[0] (即5)并使用二进制搜索查找a中的正确位置。

B[0] 属于A的后面，Timsort检查 [0] (也就是1)在B的正确位置，所以我们要看看1在哪里。

这个数在 B 的开头，我们现在知道 B 在 A 的末尾，A 在 B 的开头。

如果 B[0] 的合适位置非常接近A的起点(反之亦然)，那么这个操作就不值得了。

另外，Timsort注意到了这一点，通过增加连续的 A-only 或 B-only 胜数来增加以后进入 gallop 模式的难度。

如果快速模式是值得的，Timsort让它更容易重新进入。

简而言之，Timsort做了两件事:

  • 具有预先存在的内部结构的数组的一致性

  • 能够保持稳定的排序

以前，为了实现稳定排序，您必须使用整数将列表中的项目压缩，并将其排序为元组数组。

Code (代码)

如果您对代码不感兴趣，可以跳过这一部分。

Timsort 源码地址

ps: 后面感兴趣，可以写一个 java 版本的。

拓展阅读

基础排序算法

Guava sort

参考资料

https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399

这可能是你听说过最快的稳定排序算法