Timsort——自适应、稳定、高效排序算法

当在使用python中自带的排序算法、或者Java中的排序算法时，产生了一些好奇，他们本身运用的是什么高端的排序算法，深究、探索、查阅资料后得到了如下的认识。

Timsort介绍

Timsort是一种混合、稳定高效的排序算法，源自合并排序和插入排序，旨在很好地处理多种真实数据。它由Tim Peters于2002年实施使用在Python编程语言中。该算法查找已经排序的数据的子序列，并使用该知识更有效地对其余部分进行排序。这是通过将已识别的子序列（称为运行）与现有运行合并直到满足某些条件来完成的。从版本2.3开始，Timsort一直是Python的标准排序算法。如今，Timsort 已是是 Python、 Java、 Android平台 和 GNU Octave 的默认排序算法。

思想

算法步骤

• 根据数列大小产生minrun（为什么需要一个minrun?合并时会说到）
  • minrun是划分run的一个条件值，run的大小小于这个minrun，就要进行扩充，将后面元素填充到run中，直到符合要求等于minrun。因此说明一下minrun 的选取方式，如果待排序序列长度为 n，则我们总共会生成$\lceil \frac{n}{minrun}\rceil$个初始 run 。
    • $\lceil \frac{n}{minrun}\rceil$刚好是2的整数次幂，则归并过程将会非常“完美”，可以表述为一个满二叉树。
    • $\lceil \frac{n}{minrun}\rceil$比2的某个整数次幂稍大一点点，则到算法的最后阶段会出现一个超长 run 与一个超短 run 的合并，这是一种非常不好的的情况。
      因此，我们会选取minrun，使得$\lceil \frac{n}{minrun}\rceil$刚好是2的整数次幂或比某个2的整数次幂稍小一点的数。
      
      
  • 当数组元素个数小于64时，minrun就是数组的长度，此时就采用二分查找插入排序来进行数组排序。
    
    
    
  • 当数组元素个数大于64时，如前所述， 我们知道当 run 的数目等于或略小于2的幂时，合并两个数组最为有效。所以 Timsort 选择范围为 [32,64]的 minrun，使得原始数组的长度除以 minrun 时$\lceil \frac{n}{minrun}\rceil$等于或略小于2的幂。
    具体而言，选择数组长度的六个最高标志位，如果其余的标志位被设置，则加1：
    • 189：，取前六个最高标志位为(47)，同时最后两位为01，所以 minrun 为47+1=48，$\lceil \frac{n}{minrun}\rceil$ = 4符合条件。
    • 976：11 1101 0000，取前六个最高标志位为(61)，同时最后几位为0000，所以 minrun 为61，$\lceil \frac{n}{minrun}\rceil$ = 16符合条件。

    
    

• 依次寻找待排序序列中的run，并判断run的大小是否小于minrun，如果小于，则向后进行扩充，采用插入排序的方式将后面的元素加入到当前的run中，直到等于minrun。如果run区间的元素为逆序时，就地线性时间调整为顺序。
• 合并run
  上一步提出了一个问题，为什么需要minrun这个值来约束run的大小，因为这样做可以使得run的大小保持一个均衡，避免存在一个很短的run和一个很长的run进行合并，这样的合并操作性价比很低。此时，合并操作也需要一个规则来进行约束。
  X、Y、Z代表栈最上方的3个run的长度（下图），如果违反了下面的两条规则，则Y与X、Z中的较小者合并。规则使得合并保持近似平衡，同时在延迟合并以实现平衡，利用cache memory中新出现的runs以及使合并决策相对简单之间保持折衷。
  • $X>Y+Z$
  • $Y>Z$
    在到达数据末尾时，Timsort反复将两次运行合并到堆栈顶部，直到只剩下一次完整数据，同时满足上面两个规则结束。
    
    实际中 Timsort 合并2个相邻的 run 需要临时存储空闲，临时存储空间的大小是2个 run 中较小的 run 的大小。Timsort算法先将较小的 run 复制到这个临时存储空间，然后用原先存储这2个 run 的空间来存储合并后的 run。
    
    合并算法是用简单插入排序，依次从左到右或从右到左比较，然后合并2个 run。为了提高效率，Timsort用二分插入排序（binary merge sort）。即先用二分查找（binary search）找到插入的位置，然后再插入。（python中的比较很贵，比较比移动昂贵，故能减少比较就减少比较）

    
    
    
    
    
    
    
    
    
    

  
  
  
  

Galloping mode

在 Galloping mode 中，算法在一个 run 中搜索另一个 run 的第一个元素。通过将该初始元素与另一个 run 的第$2k-1$个元素（即1,3,5…）进行比较来完成的，以便获得初始元素所在的元素范围。这缩短了二分查找的范围，从而提高了效率。如果发现 Galloping 的效率低于二分查找，则退出 Galloping mode。
例如，我们要将 X 和 Y 这2个 run 合并，且X是较小的 run，以及 X 和 Y 已经分别是排好序的，将X复制到cache memory中，如下图所示。

二分查找会找到 X 中第一个大于 Y[0] 的元素 x，当找到 x 时，可以在合并时忽略 x 之前的元素。类似的，还可以在 Y 中找到第一个大于 X[-1] （即X最大的元素）的元素 y，当找到 y 时，可以在合并时忽略 y 之后的元素，这种查找可能在随机数中效率不会很高，但是在其他情况下有很高的效率。

当算法到达最小阈值min_gallop时，算法切换到 Galloping mode，试图利用数据中的那些可以直接排序的元素。只有当一个 run 的初始元素不是另一个 run 的前七个元素之一时，Galloping 才有用。这意味着初始阈值为7。
为了避免 Galloping mode 的缺点，合并函数会调整阈值。如果所选元素来自先前返回元素的同一数组，则min_gallop减1。否则，该值增加1，从而阻止返回到 Galloping mode 。 在随机数据的情况下，min_gallop的值会变得非常大，以至于 Galloping mode 永远不会再次发生。

算法时间复杂度

本质上 Timsort 是一个经过大量优化的归并排序，而归并排序已经到达了最坏情况下，比较排序算法时间复杂度的下界，所以在最坏的情况下，Timsort 时间复杂度为 $O(nlogn)$。在最佳情况下，即输入已经排好序，它则以线性时间运行$O(n)$。可以看出Timsort是目前最好的排序方式。

代码

以下实现的代码并不是具体完整的timsort,而是简化的，符合Timsort思想的大概实现。具体、完整的代码可以参看python源代码中的排序，或者JDK1.8中的源码，也可参照Timsort官方原始C代码：

#!/usr/bin/env python # coding=utf-8 """realize timsort""" __author__ = 'steven' def binary_search(arr, left, right, value): """ 二分查找 :param arr: 列表 :param left: 左索引 :param right: 右索引 :param value: 需要插入的值 :return: 插入值所在的列表位置 """ if left >= right: if arr[left] <= value: return left + 1 else: return left elif left < right: mid = (left + right) // 2 if arr[mid] < value: return binary_search(arr, mid + 1, right, value) else: return binary_search(arr, left, mid - 1, value) def insertion_sort(arr): """ 针对run使用二分折半插入排序 :param arr: 列表 :return: 结果列表 """ length = len(arr) for index in range(1, length): value = arr[index] pos = binary_search(arr, 0, index - 1, value) arr = arr[:pos] + [value] + arr[pos:index] + arr[index + 1:] return arr def merge(l1, l2): """ 合并 :param l1: 列表1 :param l2: 列表2 :return: 结果列表 """ if not l1: return l2 if not l2: return l1 if l1[0] < l2[0]: return [l1[0]] + merge(l1[1:], l2) else: return [l2[0]] + merge(l1, l2[1:]) def timsort(arr): """ timsort :param arr: 待排序数组 :return: """ if not arr: # 空列表 return runs, sorted_runs = [], [] new_run = [arr[0]] length = len(arr) # 划分run区，并存储到runs里，这里简单的按照升序划分，没有考虑降序的run for index in range(1, length): if arr[index] < arr[index - 1]: runs.append(new_run) new_run = [arr[index]] else: new_run.append(arr[index]) if length - 1 == index: runs.append(new_run) break # 由于仅仅是升序的run，没有涉及到run的扩充和降序的run # 因此，其实这里没有必要使用insertion_sort来进行run自身的排序 for run in runs: insertion_sort(run) # 合并runs sorted_arr = [] for run in runs: sorted_arr = merge(sorted_arr, run) print(sorted_arr) 

参考资料

• Timsort - wiki
• Timsort原理学习
• Nicolas Auger, Cyril Nicaud, Carine Pivoteau. Merge Strategies: from Merge Sort to TimSort. 2015.