9.2 高级排序：希尔、归并与分治

第 9 章 · 进阶排序｜前置：基础排序与递归｜下一章：快速、堆与非比较排序。本页先说明希尔排序的 gap，再从合并不变量推到自顶向下与自底向上的归并排序。

从短移到长步

插入排序一次只能把记录向左挪一位。元素离目标位置很远时，同一段移动会被反复执行。希尔排序让元素先跳远一点：先隔着较大的间距做插入排序，让元素走长步；间距缩到 1 时，数组已经接近有序。

归并排序把大问题拆成两半，分别排序再合并。下一章的快速排序也使用分治，但先分区，再分别处理两侧；两者把工作放在了不同的位置。

统一代码合同

三个函数都返回新列表，不修改输入，并且对每个元素只计算一次 key。输入迭代器会被消耗，元素对象仍按引用共享；比较只看排序键，不拿记录中的原位置打破平局。键必须具有一致的顺序，排除 NaN，并在排序期间保持不变。装饰记录占 Θ(n) 辅助空间，返回列表另占 Θ(n) 输出空间；表格另列排序核心的成本，默认求 key 与比较为常数操作。

def _decorate(values, key):
    key_function = (lambda item: item) if key is None else key
    return [
        [key_function(item), index, item]
        for index, item in enumerate(values)
    ]

def _values(records):
    return [record[2] for record in records]

def shell_sort(values, key=None):
    """使用 Knuth gap 序列的希尔排序；不保证稳定。"""
    records = _decorate(values, key)
    n = len(records)
    gap = 1
    while gap < n // 3:
        gap = 3 * gap + 1

    while gap >= 1:
        for index in range(gap, n):
            current = records[index]
            hole = index
            while hole >= gap and records[hole - gap][0] > current[0]:
                records[hole] = records[hole - gap]
                hole -= gap
            records[hole] = current
        gap //= 3
    return _values(records)

def _merge_records(left, right):
    merged = []
    left_index = 0
    right_index = 0
    while left_index < len(left) and right_index < len(right):
        if not right[right_index][0] < left[left_index][0]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged

def merge_sort(values, key=None):
    """自顶向下稳定归并排序。"""
    records = _decorate(values, key)

    def sort(part):
        if len(part) <= 1:
            return part
        middle = len(part) // 2
        left = sort(part[:middle])
        right = sort(part[middle:])
        return _merge_records(left, right)

    return _values(sort(records))

def merge_sort_bottom_up(values, key=None):
    """自底向上稳定归并排序。"""
    records = _decorate(values, key)
    width = 1
    while width < len(records):
        merged_pass = []
        for left in range(0, len(records), 2 * width):
            middle = min(left + width, len(records))
            right = min(left + 2 * width, len(records))
            merged_pass.extend(
                _merge_records(records[left:middle], records[middle:right])
            )
        records = merged_pass
        width *= 2
    return _values(records)

if __name__ == "__main__":
    data = [38, 27, 43, 3, 9, 82, 10]
    print("shell:   ", shell_sort(data))
    print("top-down:", merge_sort(data))
    print("bottom-up:", merge_sort_bottom_up(data))
    print("original:", data)

示例输出：

shell:    [3, 9, 10, 27, 38, 43, 82]
top-down: [3, 9, 10, 27, 38, 43, 82]
bottom-up: [3, 9, 10, 27, 38, 43, 82]
original: [38, 27, 43, 3, 9, 82, 10]

希尔排序：gap 必须说清

本实现使用 Knuth 序列：

1, 4, 13, 40, ...

程序从 1 开始，在 gap < n // 3 时继续生成 3*gap+1，随后反向缩小。它不一定选“小于 n 的最大增量”：例如 n=14 时从 4 开始，不会取 13。例如 gap 为 4 时，下标 0, 4, 8... 组成一条子序列；下标 1, 5, 9... 组成另一条。每条都做插入排序。

数据：[9, 8, 3, 7, 5, 6, 4, 1]
gap=4 后：[5, 6, 3, 1, 9, 8, 4, 7]，各隔 4 位的序列有序
gap=1 时，再做一次普通插入排序
结果：[1, 3, 4, 5, 6, 7, 8, 9]

任何最终包含 gap=1 的合法序列都能完成排序，但性能会随 gap 序列改变。不能给“希尔排序”写一个脱离序列的统一紧确时间界。对本页使用的 Knuth 增量，Princeton 教材给出 O(n^(3/2)) 的比较次数上界；这不代表其他增量也有同一结论：Elementary Sorts。

希尔排序的核心可原地运行，算法辅助空间 O(1)。跨 gap 移动可能越过相等记录，因此不保证稳定。

归并排序：先证明合并

合并函数接收两个已排序列表。每一步只需比较两边尚未取走的第一个记录：

left  = [27, 38, 43]
right = [3, 9, 10, 82]

取 3，取 9，取 10，取 27，取 38，取 43，最后接上 82

循环不变量是：merged 恰好是两份输入合并后最小的 len(merged) 条记录，并已排好；两边游标分别指向尚未取走的第一条。任意一边耗尽后，另一边剩余部分已经有序，可以直接接上。

代码用 not right_key < left_key 判断：右键不更小时先取左边，只依赖 < 运算。相等时也取左边记录。左半来自输入中更早的位置，因此两个相等键保持原次序，归并排序稳定。

自顶向下：画递归树

用八个元素更容易看清层数：

[8 7 6 5 4 3 2 1]
        /               \
[8 7 6 5]             [4 3 2 1]
   /      \               /      \
[8 7]   [6 5]          [4 3]   [2 1]
 / \     / \            / \     / \
[8][7] [6][5]          [4][3] [2][1]

当 n 是 2 的幂时，每层合并恰好处理 n 个元素，共 log₂ n 层。一般 n 时，层数至多 ceil(log₂ n)，各元素所在路径深度仍是对数量级，所以本实现对非空规模增长的时间为 Θ(n log n)。空输入和单元素只需常数工作。这个推导只把“基本操作次数”与 n 关联，不把它换算成某台机器上的毫秒数。

同时存活的切片、子结果和合并缓冲的峰值为 O(n)，递归栈为 O(log n)。但多层反复创建切片和结果列表，整个排序过程中累计分配的引用槽位为 Θ(n log n)；它们不会一直同时存活。复用辅助数组可以减少这种分配成本。

自底向上：宽度翻倍

迭代版从长度 1 的 run 开始：

width=1  [8]+[7] [6]+[5] [4]+[3] [2]+[1]
width=2  [7 8]+[5 6]     [3 4]+[1 2]
width=4  [5 6 7 8]+[1 2 3 4]
width=8  完成

right = min(left + 2 * width, n) 处理末尾不足一整组的情况。自底向上版本去掉 O(log n) 递归栈，但合并仍需要 O(n) 缓冲；“没有递归”不等于“原地”。

Princeton 的归并资料给出了自顶向下、自底向上和比较下界：Mergesort。

快速排序留到下一章

先看一个满足分区要求的结果，暂不要求两侧内部有序：

数组：[10, 7, 8, 9, 1, 5]
pivot=5
分区后：[1, 5, 8, 9, 10, 7]

支点左边不大于它，右边不小于它，再递归处理两侧。对互异键，均匀随机选择支点可得到期望 O(n log n)。大量重复键时还要选择合适分区策略：把所有相等键都送往同一侧的朴素二路规则，即使随机选支点也可能持续产生坏分区。下一章用三路分区直接跳过等值区；最坏 O(n²) 仍可能发生。Princeton 的快排材料把随机化、相等键和坏分区分开讨论：Quicksort。

下一章实现随机三路快排、堆排序，以及计数、基数和桶排序。

专业速查

算法	时间	算法辅助空间	稳定	备注
Shell（Knuth gap）	依 gap 序列；所引资料给出 O(n^(3/2)) 上界	O(1)	否	长距离移动，最后 gap=1
归并（自顶向下）	Θ(n log n)	O(n) 缓冲 + O(log n) 栈	是	相等时先取左侧
归并（自底向上）	Θ(n log n)	O(n) 缓冲	是	无递归栈

本页公共函数为了不修改输入，还会创建 O(n) 的装饰记录与结果；这部分不应悄悄混进“核心原地”说法中。

标准库边界

Python 保证排序稳定，其文档说明 Timsort 会利用输入中已有的顺序；这不等于本页固定二分归并也会自动获得相同的自适应效果：Python Sorting HOWTO。

Java SE 25 的 Arrays.sort(Object[]) 文档保证稳定，并把当前实现描述为稳定、自适应的迭代归并排序。基本类型数组有不同的实现说明。它们是版本化的 API 文档，不是“Java 语言永远使用某一种算法”的定理：Java SE 25 Arrays。

从长步回到分治

希尔排序的性能离不开 gap 序列；不写增量口径，就没有一张可信的复杂度表。归并排序的核心则是合并两个有序序列，递归或迭代只决定 run 如何产生。相等时先取左侧，才保住稳定性。

下一章实现 随机三路快排、堆排与非比较排序，再把这些保证放进统一选型表。