Timsort 算法

1 基础理解

1.1 定义和原理

Timsort 算法是一种 稳定的 混合排序算法，结合了归并、插入排序的优点，利用了数组中已存在的有序序列（run）来提高排序效率。对小规模数据用插入排序，大规模数据用归并排序。平均时间复杂度为 O(nlogn)，适合处理部分有序的数据。

Python 的内置排序函数 sorted() 和列表的 sort() 方法底层使用了 Timsort。

1.2 工作原理

1. 先将数组划分为多个有序子数组run，每个run是一个非递减或非递增的连续子序列，Timsort 会自动检测这些 run，若一个 run 是递减的，则将其反转为递增的。

   如 [3, 4, 3, 2, 1, 7, 8, 9]，检测到以下 run：
      [3, 4]（递增）
      [3, 2, 1]（递减，反转后为 [1, 2, 3]）
      [7, 8, 9]（递增）
   

2. 计算一个最小 run 长度 minrun，一般在 [32,64] 区间中取值，具体取决于数组总长。若某个 run 长度小于 minrun，则用 插入排序 将其扩展到 至少 minrun 的长度

   如长为 100 的数组，minrun 可能被设置为 32。
   若检测到一个长为 10 的 run，则用插入排序将其扩展到至少 32 个元素
   

3. 归并排序：若所有 run 的长度均满足要求，则将这些 run 做二路归并，其中，Timsort 使用 galloping mode 归并策略。

    Galloping Mode：
      二路归并中，若出现连续的“一边倒”情况 —— 一个 run 的元素 连续多次小于 另一个 run 的元素），Timsort 会切换到 galloping mode。
      这种模式下，算法会以指数级的速度跳过元素，从而减少不必要的比较。
   

4. 归并时，Timsort 用 临时数组 存中间结果。为减少内存开销，Timsort 会预分配一个足够大的临时数组，在归并途中复用这个数组。

2 算法实现

2.1 Python 代码实现

2.1.1 代码

#python 做升序排序

MIN_MERGE = 32

def calc_min_run(n):
    """计算最小的运行长度（run）"""
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1 
        n >>= 1 
    return n + r

def insertion_sort(arr, left, right):
    """插入排序"""
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        
def merge(arr, l, m, r):
    """合并两个有序数组"""
    len1, len2 = m - l + 1, r - m
    left, right = [], []
    for i in range(len1):
        left.append(arr[l + i])
    for i in range(len2):
        right.append(arr[m + 1 + i])

    i, j, k = 0, 0, l
    while i < len1 and j < len2:
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len1:
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len2:
        arr[k] = right[j]
        j += 1
        k += 1

def timsort(arr):
    n = len(arr)
    min_run = calc_min_run(n)

    # 对每个小块进行插入排序
    for start in range(0, n, min_run):
        end = min(start + min_run - 1, n - 1)
        insertion_sort(arr, start, end)

    # 合并有序块
    size = min_run
    while size < n:
        for left in range(0, n, size * 2):
            mid = min(n - 1, left + size - 1)
            right = min((left + 2 * size - 1), (n - 1))
            if mid < right:
                merge(arr, left, mid, right)
        size *= 2

# 示例
if __name__ == "__main__":
    arr = [5, 9, 1, 3, 4, 6, 6, 3, 2]
    print("原始数组:", arr)
    timsort(arr)
    print("排序后数组:", arr)

2.1.2 核心逻辑

计算最小运行长度（calc_min_run(n)）

目的：确定每个小块的最小长度（min run），用于后续的插入排序。
性能优化：通过 位运算 高效计算 min_run，避免复杂的数学运算

MIN_MERGE = 32

def calc_min_run(n):
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r

逻辑解释：

1. 初始设定 MIN_MERGE = 32，表示每个小块的最小长度通常至少为 32。

2. r 变量（0、1 两种取法）用于累积 n 的最低位，确保最终的 min_run 能够在一定范围内动态调整。

3. 通过位运算（n >>= 1 和 r |= n & 1），逐步将 n 右移并累积最低位，直到 n 小于 MIN_MERGE。

4. 最终返回 n + r，这确保了 min_run 的值在合理范围内，同时考虑了数组长度的具体情况。

   补充：
    1、n&1 按位与（同1为1，其他为0）：
    	若 n = 5 = 101B,则 101 & 001 = 001，n&1=1
    	若 n = 4 = 100B,则 100 & 001 = 000，n&1=0
    总结：n&1 结果取决于 n 的二进制最低位，若最低位是1，结果为1；若最低位是0，结果为0。
    
    2、r |= ... ：按位或赋值，r 与 后面表达式 进行按位或运算，并将结果赋值给 r
   
    3、按位或（至少一个为1时，结果为1，其他都是0 —— 有1为1，其他为0）：
    	若 r = 0，n & 1 = 1，则 r |= n & 1 ，使 r 变为 1
    	若 r = 0，n & 1 = 0，则 r |= n & 1， 使 r 变为 0
    	
    4、‌>> 是 按位右移运算符
     	n >>= 1 ：n 的二进制向右移一位，等效于 n除以2（取整）
   

综上，这段代码的做法就是：将数组总长 n，不断的除 2 取整 ，直至 n < MIN_MERGE，最终返回这个 n 与 r (0 或 1) 的加和。

插入排序（insertion_sort(arr, left, right)）

目的：对数组的某个子区间 [left, right] 进行插入排序。
 
性能优化：插入排序在小规模数据上效率很高，且实现简单，时间复杂度为 O(n²)，部分有序时效率较高。通过直接在原数组上操作，避免额外的内存开销。

def insertion_sort(arr, left, right):
    """ 
    插入排序： 
		设 arr[left] 是已排部分的第一个元素，
		则从 left + 1 起处理未排序部分的元素。 
	"""
    #从 left + 1 开始遍历到 right
    for i in range(left + 1, right + 1):
        key = arr[i]
        #从当前元素的前一个位置开始，向前遍历已排序部分
        j = i - 1
        #arr[j]大于当前元素key，则 arr[j] 后移一位
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1 
        arr[j + 1] = key 

逻辑解释：

1. 从 left + 1 开始遍历到 right，将每个元素 key 插入到已排序部分的合适位置。
2. 内层循环将大于 key 的元素依次向后移动，为 key 腾出插入位置。

例如，对如下数组中索引为 [0,15] 的子序列做插入排序（小白请看，糕手略过）：

这放个图，方便对照

第 1 轮 insertion_sort(arr, left, right)：insertion_sort(arr, 0, 15) ——
	for i in range(1, 16) ：遍历数组中索引为 [1,15] 的元素
       第 1 轮 for 循环 —— " i = 1 "
 	   	  key = arr[i] ： arr[1] = 7 —— key 即当前元素 arr[1]
    	  j = i - 1 ：j = 0 —— 当前元素的前一个元素索引 j
    	  
          while j >= left and arr[j] > key :
			   第 1 轮 判断 0 >= 0 and arr[0] > 7 
			 		  因 arr[0] = 5 < key = 7，故跳过 while，执行后面
			 		  
	      arr[j + 1] = key : arr[1] = key = 7
	      
	      —— 当前元素 arr[i] = arr[1] = 7 与前一个元素 arr[i-1] = arr[0] = 5 符合升序排序，
	      	 所以，没进 while 循环，j 未变动，后面的 arr[j + 1] = key 相当于未进行操作。

       第 2 轮 for 循环 —— " i = 2 " ： 后移判断下一个元素，当前元素 arr[i] 即 arr[2]
          key = arr[i] ： arr[2] = 2 —— key 即当前元素 arr[2]
          j = i - 1 ：j = 1 —— 当前元素的前一个元素索引 j
          
          while j >= left and arr[j] > key：
           	第 1 轮 判断 " 1 >= 0 and arr[1] = 7 > 2 " —— 前一个 > 当前这个，进循环体
           		arr[j + 1] = arr[j] ：arr[2] = arr[1] ——  前一个元素 赋到 当前位置，达到大数后移的升序目的（当前位置 arr[j+1] 和前一个位置 arr[j] 都是这个大的数）
            	j -= 1 ：j = 0 —— 索引 j 前移 1 位
            第 2 轮 进 while ，做条件判断 " 0 >= 0 and arr[0] = 5 > 2
            先去吃个饭，下午再写

2.2 Java 代码实现

//java
import java.util.Arrays;

public class TimSort {
    private static final int MIN_MERGE = 32;

    public static void timSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i += MIN_MERGE) {
            insertionSort(arr, i, Math.min((i + MIN_MERGE - 1), (n - 1)));
        }
        for (int size = MIN_MERGE; size < n; size = 2 * size) {
            for (int left = 0; left < n; left += 2 * size) {
                int mid = left + size - 1;
                int right = Math.min((left + 2 * size - 1), (n - 1));
                if (mid < right) {
                    merge(arr, left, mid, right);
                }
            }
        }
    }

    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] leftArray = Arrays.copyOfRange(arr, left, mid + 1);
        int[] rightArray = Arrays.copyOfRange(arr, mid + 1, right + 1);
        int i = 0, j = 0, k = left;
        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k++] = leftArray[i++];
            } else {
                arr[k++] = rightArray[j++];
            }
        }
        while (i < leftArray.length) {
            arr[k++] = leftArray[i++];
        }
        while (j < rightArray.length) {
            arr[k++] = rightArray[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 1, 4, 6, 2};
        timSort(arr);
        System.out.println("Sorted array using Tim Sort: " + Arrays.toString(arr));
    }
}

2.3 C 代码实现

//C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN_MERGE 32

void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    memcpy(L, arr + left, n1 * sizeof(int));
    memcpy(R, arr + mid + 1, n2 * sizeof(int));
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }
}

void timSort(int arr[], int n) {
    for (int i = 0; i < n; i += MIN_MERGE) {
        insertionSort(arr, i, (i + MIN_MERGE - 1) < (n - 1) ? (i + MIN_MERGE - 1) : (n - 1));
    }
    for (int size = MIN_MERGE; size < n; size = 2 * size) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = (left + 2 * size - 1) < (n - 1) ? (left + 2 * size - 1) : (n - 1);
            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
}

int main() {
    int arr[] = {5, 3, 1, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    timSort(arr, n);
    printf("Sorted array using Tim Sort: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

3 逻辑细节

3.1 如何选择合适的 min_run？

参数 min_run 决定了数组被分割成 多大的小块 进行插入排序。

通常，min_run 的值在 32 到 64 之间。Python 的 Timsort 实现中，默认值是 32。

min_run 的值可以这样计算（能根据数组长，动态调整）：

#python
MIN_MERGE = 32

def calc_min_run(n):
    """计算最小的运行长度（run）"""
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1 # 0、1 两种取值
        n >>= 1 # n/2 取整
    return n + r

3.2 如何处理边界情况？例如数组长度小于 min_run

若 数组长 < min_run，可直接对整个数组进行插入排序。因为插入排序在小规模数据上的性能很好，而且实现简单。

#python
if len(arr) < min_run:
    insertion_sort(arr, 0, len(arr) - 1)

4 性能和优化细节

4.1 为什么 Timsort 比纯归并排序或插入排序更高效？

• Timsort 结合了两种排序算法的优点：

   插入排序：在小规模数据上效率很高，且实现简单。
   归并排序：在大规模数据上效率很高，且稳定。
  

• 利用了自然有序序列
  Timsort 能识别数组中已存在的有序序列（run），并利用其减少归并次数和复杂度。这使 Timsort 在处理 部分有序的数据 时特别高效。

• 稳定性和适应性
  Timsort 是一种稳定的排序算法，能适应不同的数据分布，从完全随机到完全有序的数据都能高效处理。

4.2 Timsort 在不同数据分布下的性能表现如何？

（1）完全随机的数据

• Timsort 的性能接近归并排序，时间复杂度为 O(nlogn)
• 因为数据完全随机，没有太多的自然有序序列，因此主要依赖于插入排序和归并排序的组合。

（2）部分有序的数据

• 性能优势明显。可利用已存在的有序序列（run），减少归并的次数和复杂度。
• 时间复杂度接近 O(n)，在某些情况下甚至可以达到线性时间复杂度。

（3）已经排序的数据

• Timsort 的性能最佳。由于整个数组已经有序，Timsort 可以直接将整个数组视为一个有序序列，时间复杂度为 O(n)。这是 Timsort 的显著优势，因为它能够高效处理已经部分排序的数据。

4.3 如何根据实际需求调整 Timsort 的参数以优化性能？

只提供了优化建议方向，还需要在实际项目中具体实践。

（1）大规模数据排序

较大的 min_run 值可以减少归并的次数，但会增加插入排序的开销。可通过实验和性能测试来选择最优的 min_run 值。通常，min_run 在 32 ~ 64 间是一个较好的选择。

（2）性能敏感的排序任务

可以对 Timsort 进行微调，如

• 优化插入排序的实现，减少不必要的操作。
• 使用更高效的归并操作，减少内存开销
• 根据数据的特性调整 min_run 的值

4.4 改进方向

• 可以利用多核处理器的优势，将 Timsort 的归并阶段并行化（在归并多个有序块时，可以将每个归并任务分配给不同的线程），使其支持多线程或并行排序。
• 归并操作中，可以使用原地归并（in-place merge）算法，如用三指针原地归并，减少额外的内存开销。
• 也可以适用于链表排序。由于链表的随机访问效率较低，可对归并操作进行优化，减少随机访问的次数。
• 对无法全部加载到内存的大规模数据，可与外部排序算法结合，如：将数据分块加载到内存中，用 Timsort 对每个块排序，然后将排序后的块写入磁盘，最后进行多路归并。
• 也可以结合快速排序的分区思想，对 Timsort 进行优化。如在归并阶段，可用快排的分区算法来减少归并次数。