Timsort——你从未听说过的最快的排序算法

Timsort 是一种对实际数据高效的排序算法，并非源于学术实验室。Tim Peters 于 2001 年为 Python 编程语言创建了 Timsort。Timsort 首先分析待排序的列表，然后根据分析结果选择合适的排序方法。

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

Timsort 的大 O 符号是 O(n log n)。要了解大 O 符号，请阅读此文。

Timsort 的排序时间与归并排序相同，比你可能知道的大多数其他排序方法都要快。Timsort 实际上利用了插入排序和归并排序，你很快就会看到。

Peters 设计 Timsort 是为了利用大多数现实世界数据集中存在的已排序元素。它将这些已排序元素称为“自然运行”。它对数据进行迭代，将元素收集到运行中，并同时将这些运行合并为一个运行。

数组中的元素少于 64 个

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

插入排序是一种简单的排序方法，它对小列表最有效。对于较大的列表，它的速度相当慢，但对于小列表，它的速度非常快。插入排序的思路如下：

逐一查看元素
通过在正确的位置插入元素来构建排序列表

在这种情况下，我们将新排序的元素插入到一个新的子数组中，该子数组从数组的开头开始。

下面是一个显示插入排序的 gif：

关于跑步的更多信息

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

因此，如果运行次数减少，它将看起来像这样（其中运行次数以粗体显示）：

如果不减少，它看起来会像这样：

最小运行 (minrun) 的大小取决于数组的大小。算法会选择最小运行，以便随机数组中的大多数运行长度等于或变为最小运行。当运行次数等于或略小于 2 的幂时，合并两个数组会更高效。Timsort 选择最小运行来尝试确保这种效率，方法是确保最小运行等于或小于 2 的幂。

该算法从 32 到 64（含）的范围内选择 minrun。它选择 minrun 的条件是，原始数组的长度除以 minrun 后等于或略小于 2 的幂。

如果运行的长度小于最小运行，则计算该运行相对于最小运行的长度。使用这个新的数字，在运行之前获取那么多元素，然后执行插入排序来创建新的运行。

因此，如果 minrun 为 63 且运行长度为 33，则执行 63-33 = 30。然后从运行结束之前抓取 30 个元素，因此这是来自 run[33] 的 30 个项目，然后执行插入排序以创建新的运行。

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

合并

Timsort 现在会执行归并排序，将运行结果合并在一起。然而，Timsort 会确保在归并排序过程中保持稳定性和合并平衡。

为了保持稳定性，我们不应该交换两个相等值的数字。这不仅能保持它们在列表中的原始位置，还能提高算法的执行速度。我们稍后会讨论合并余额。

当 Timsort 找到运行结果时，它会将它们添加到堆栈中。一个简单的堆栈如下所示：

想象一下一叠盘子。你不能从底部取盘子，所以你必须从顶部取。同样的道理也适用于堆叠。

Timsort 在执行归并排序时，会尝试平衡两种相互竞争的需求。一方面，我们希望尽可能延迟合并，以便利用后续可能出现的模式。另一方面，我们更希望尽快进行合并，以便利用刚刚找到的运行仍然位于内存层级较高位置的运行。我们也不能将合并延迟“太久”，因为记住尚未合并的运行会消耗内存，而堆栈的大小是固定的。

为了确保我们达成这一妥协，Timsort 会跟踪堆栈中最近的三个项目，并创建两个必须适用于这些项目的定律：

A > B + C
B > C

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

用蒂姆·彼得斯自己的话来说：

事实证明，一个很好的折衷方案是保留堆栈条目上的两个不变量，其中 A、B 和 C 是三个最右边尚未合并的切片的长度

通常，合并不同长度的相邻运行很困难。更困难的是，我们必须保持稳定性。为了解决这个问题，Timsort 会预留临时内存。它会将两个运行中较小的一个（分别称为运行 A 和运行 B）放入该临时内存中。

奔腾

当 Timsort 合并 A 和 B 时，它注意到一个运行结果已经连续多次“获胜”。如果结果发现 A 运行结果包含的数字远小于 B 运行结果，那么 A 运行结果最终会回到原来的位置。合并这两个运行结果需要大量工作，最终却一无所获。

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

两个示例运行 A 和 B 的图像。运行必须严格增加或减少，这就是选择这些数字的原因。

然后，Timsort 将进入飞驰模式。Timsort 不会将 A[0] 和 B[0] 相互比较，而是执行二分查找，以查找 a[0] 中 b[0] 的适当位置。这样，Timsort 可以将 A 的整个部分移动到位。然后，Timsort 在 B 中搜索 A[0] 的适当位置。Timsort 会一次性将 B 的整个部分移动到位。

让我们看看实际效果。Timsort 检查 B 0，并使用二分查找在 A 中寻找正确的位置。

嗯，B[0] 应该位于 A 列表的末尾。现在 Timsort 检查 A 0是否位于 B 的正确位置。所以我们要看看数字 1 应该位于哪里。这个数字应该位于 B 的开头。现在我们知道 B 应该位于 A 的末尾，而 A 应该位于 B 的开头。

事实证明，如果 B[0] 的合适位置非常靠近 A 的开头（反之亦然），则此操作不值得。因此，如果疾驰模式没有效果，它会迅速退出。此外，Timsort 会注意到这一点，并通过增加进入疾驰模式所需的连续 A 或 B 获胜次数，使以后进入疾驰模式变得更加困难。如果疾驰模式有效，Timsort 会让重新进入变得更容易。

简而言之，Timsort 在两件事上做得非常好：

在具有预先存在的内部结构的阵列上表现出色
能够保持稳定的排序

以前，为了实现稳定的排序，您必须将列表中的项目与整数压缩在一起，然后将其排序为元组数组。

代码

如果您对代码不感兴趣，请跳过此部分。本节下面还有更多信息。

以下源代码基于我和 Nanda Javarma 的工作。该源代码并不完整，也与 Python 官方的 sorted() 源代码有所不同。这只是我为了大致了解 Timsort 而实现的简化版 Timsort。如果您想完整地了解 Timsort 的原始源代码，请点击此处查看。Timsort 官方是用 C 语言实现的，而不是 Python。

# based off of this code https://gist.github.com/nandajavarma/a3a6b62f34e74ec4c31674934327bbd3
# Brandon Skerritt
# https://skerritt.tech

def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
Insertion sort that timsort uses if the array size is small or if
the size of the "run" is small
"""
def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
    return the_array

def merge(left, right):
    """Takes two sorted lists and returns a single sorted list by comparing the
    elements one at a time.
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]

    # for every i in the range of 1 to length of array
    for i in range(1, length):
        # if i is at the end of the list
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        # if the i'th element of the array is less than the one before it
        if the_array[i] < the_array[i-1]:
            # if new_run is set to None (NULL)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        # else if its equal to or more than
        else:
            new_run.append(the_array[i])

    # for every item in runs, append it using insertion sort
    for item in runs:
        sorted_runs.append(insertion_sort(item))

    # for every run in sorted_runs, merge them
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

Timsort 实际上是 Python 内置的，所以这段代码仅供参考。要使用 Timsort，只需输入：

list.sort()

或者

sorted(list)

如果您想掌握 Timsort 的工作原理并对其有所了解，我强烈建议您尝试自己实现它！

本文基于 Tim Peters 对 Timsort 的原始介绍，可在此处找到。

👋 你喜欢这篇文章吗？订阅我的邮件列表，这样每当我发布新内容时（大约每3-6周一次）你都会收到邮件通知✨😁 https://pages.convertkit.com/2ffbe6834c/8444e0640e

文章来源：https://dev.to/brandonskerritt/timsort-the-fastest-sorting-algorithm-you-ve-never-heard-of-2ake