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跟踪栈上最近的三个项目，并创建两个必须符合这些项目的规则:
-
A > B+C
-
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 (代码)
如果您对代码不感兴趣，可以跳过这一部分。
ps: 后面感兴趣，可以写一个 java 版本的。
拓展阅读
参考资料
https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399
