如何优化Python版Timsort算法：替换为二分插入排序及添加Galloping归并

1. 用二分插入排序替代普通插入排序 #

普通插入排序在有序子序列中逐个比较移动，二分插入排序通过二分查找快速定位插入位置，将比较复杂度从O(k)降到O(logk)（k为子序列长度），提升小序列排序效率。

替换原insertion函数的实现：

def binary_insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        # 取出当前要插入的元素
        key = arr[i]
        # 二分查找在[left, i-1]中找到第一个大于key的位置
        low = left
        high = i - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] > key:
                high = mid - 1
            else:
                low = mid + 1
        # 将[low, i-1]的元素向后移动一位
        for j in range(i, low, -1):
            arr[j] = arr[j-1]
        # 插入key到正确位置
        arr[low] = key

2. 归并过程启用Galloping模式 #

Galloping模式是Timsort的核心优化：当归并时其中一个有序序列连续多次被选中取元素，切换到二分查找批量取元素，减少循环迭代次数。需要先实现两个辅助定位函数，再修改归并逻辑。

辅助定位函数 #

def gallop_left(key, arr, start, end):
    # 在arr[start..end]（升序）中找到第一个大于key的位置
    if start > end:
        return start
    low = start
    high = end + 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] > key:
            high = mid
        else:
            low = mid + 1
    return low

def gallop_right(key, arr, start, end):
    # 在arr[start..end]（升序）中找到第一个大于等于key的位置
    if start > end:
        return start
    low = start
    high = end + 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] >= key:
            high = mid
        else:
            low = mid + 1
    return low

优化后的归并函数 #

def merge_with_galloping(arr, start, mid, end):
    # 拆分两个有序子数组
    left_len = mid - start + 1
    right_len = end - mid
    left_arr = arr[start:mid+1]
    right_arr = arr[mid+1:end+1]

    i = j = 0
    k = start
    # 触发gallop模式的连续匹配阈值（Timsort标准值为7）
    gallop_threshold = 7
    left_gallop_count = 0
    right_gallop_count = 0

    while i < left_len and j < right_len:
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
            left_gallop_count += 1
            right_gallop_count = 0
            # 触发左数组的gallop模式
            if left_gallop_count >= gallop_threshold:
                pos = gallop_right(right_arr[j], left_arr, i, left_len - 1)
                arr[k:k + pos - i] = left_arr[i:pos]
                k += pos - i
                i = pos
                left_gallop_count = 0
        else:
            arr[k] = right_arr[j]
            j += 1
            right_gallop_count += 1
            left_gallop_count = 0
            # 触发右数组的gallop模式
            if right_gallop_count >= gallop_threshold:
                pos = gallop_left(left_arr[i], right_arr, j, right_len - 1)
                arr[k:k + pos - j] = right_arr[j:pos]
                k += pos - j
                j = pos
                right_gallop_count = 0
        k += 1

    # 复制剩余元素
    while i < left_len:
        arr[k] = left_arr[i]
        i += 1
        k += 1
    while j < right_len:
        arr[k] = right_arr[j]
        j += 1
        k += 1

完整优化后的Timsort代码 #

def calcMinRun(n):
    r = 0
    while n >= 32:
        r |= n & 1
        n >>= 1
    return n + r

def binary_insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        key = arr[i]
        low = left
        high = i - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] > key:
                high = mid - 1
            else:
                low = mid + 1
        for j in range(i, low, -1):
            arr[j] = arr[j-1]
        arr[low] = key

def gallop_left(key, arr, start, end):
    if start > end:
        return start
    low = start
    high = end + 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] > key:
            high = mid
        else:
            low = mid + 1
    return low

def gallop_right(key, arr, start, end):
    if start > end:
        return start
    low = start
    high = end + 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] >= key:
            high = mid
        else:
            low = mid + 1
    return low

def merge_with_galloping(arr, start, mid, end):
    left_len = mid - start + 1
    right_len = end - mid
    left_arr = arr[start:mid+1]
    right_arr = arr[mid+1:end+1]

    i = j = 0
    k = start
    gallop_threshold = 7
    left_gallop_count = 0
    right_gallop_count = 0

    while i < left_len and j < right_len:
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
            left_gallop_count += 1
            right_gallop_count = 0
            if left_gallop_count >= gallop_threshold:
                pos = gallop_right(right_arr[j], left_arr, i, left_len - 1)
                arr[k:k + pos - i] = left_arr[i:pos]
                k += pos - i
                i = pos
                left_gallop_count = 0
        else:
            arr[k] = right_arr[j]
            j += 1
            right_gallop_count += 1
            left_gallop_count = 0
            if right_gallop_count >= gallop_threshold:
                pos = gallop_left(left_arr[i], right_arr, j, right_len - 1)
                arr[k:k + pos - j] = right_arr[j:pos]
                k += pos - j
                j = pos
                right_gallop_count = 0
        k += 1

    while i < left_len:
        arr[k] = left_arr[i]
        i += 1
        k += 1
    while j < right_len:
        arr[k] = right_arr[j]
        j += 1
        k += 1

def timSort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    minRun = calcMinRun(n)
    for start in range(0, n, minRun):
        end = min(start + minRun - 1, n - 1)
        binary_insertion_sort(arr, start, end)
    size = minRun
    while size < n:
        for left in range(0, n, 2 * size):
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            if mid < right:
                merge_with_galloping(arr, left, mid, right)
        size *= 2
    return arr

关键说明 #

• 二分插入排序：针对Timsort中长度较小的run子序列，减少比较次数，提升排序效率。
• Galloping模式：当归并时某一序列连续多次被选中，通过二分查找批量定位并复制元素，避免逐个循环比较，大幅降低归并阶段的迭代次数。
• 归并优化：原归并函数在原数组上逐个移动元素效率低下，优化后先复制子数组再归并，配合Galloping模式进一步提升性能。

内容的提问来源于stack exchange，提问作者Arnav Sharma