排序把相同数据组织成确定的顺序，选择问题只要求某个名次或一小部分元素。需要前十名时不一定要把一千万条记录全部排序；是否保留原始同分顺序、是否能全部载入内存，也会影响方案。
稳定归并为什么成立
归并排序先递归排好左右两半，再反复取两边当前较小的元素。不变量是：输出已经有序，尚未输出的最小元素必在两侧头部。两侧相等时先取左边，能让先出现的记录继续在前，因此排序稳定。
def merge_sort(values, key=lambda x: x):
if len(values) <= 1:
return list(values)
mid = len(values) // 2
left = merge_sort(values[:mid], key)
right = merge_sort(values[mid:], key)
result = []
i = j = 0
while i < len(left) and j < len(right):
if key(left[i]) <= key(right[j]):
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
if __name__ == '__main__':
print(merge_sort([(2, 'a'), (1, 'x'), (2, 'b')], key=lambda row: row[0]))
例子按分数排序后，相同分数的 a 仍在 b 前。每次合并扫描全部待合并元素，每层总工作 O(n)，递归深度 O(log n)，所以时间 O(n log n)。当前实现为清楚展示分治而创建切片和结果列表，峰值额外空间 O(n)，还要计入 O(log n) 的调用栈；它不是原地排序。
不同算法解决不同约束
| 方法 | 主要成本 | 关键条件或取舍 |
|---|---|---|
| 插入排序 | 最坏 O(n²) | 小规模、近乎有序时有用，可稳定 |
| 归并排序 | O(n log n) | 容易稳定，通常需额外空间，适合外部归并 |
| 快速排序 | 随机枢轴期望 O(n log n)，最坏 O(n²) | 分区与重复值处理影响退化，常见原地版不稳定 |
| 堆排序 | O(n log n) | 可原地，通常不稳定，局部性取舍不同 |
| 计数/基数排序 | 依赖键域或位数 | 不能脱离键范围说“排序必然 n log n” |
比较排序的 Ω(n log n) 下界来自不同排列所需的区分信息，不适用于利用有限整数键域的计数排序。计数排序的桶范围若远大于元素数量，时间与空间可能得不偿失。
Python sorted 和 list.sort 是稳定排序，日常代码优先使用它们，再通过明确的键函数表达规则。需要降序且保持同分顺序时，可使用 reverse=True，不必先升序再手工反转全部记录。
Top-K与外存
持续接收数据并保留最大的K个值时，可维护容量K的最小堆，时间 O(n log K)、空间 O(K)。快速选择通过分区缩小候选范围，随机化后期望 O(n)，但若最后需要有序输出，还要对选中的K个值排序。
数据超出内存时，先分块生成有序文件，再多路归并。此时磁盘读取和缓冲区是核心约束，不应只比较CPU上的渐近复杂度。堆的具体使用见树与堆。
练习与面试自查
给归并增加比较次数计数，用有序、逆序、全相等与随机输入比较。验证输出有序且元素及其重复次数保持不变；稳定性要用带身份的同键记录检查，只比较数字序列无法发现稳定性丢失。
面试中说明：归并在相等时改取右边会怎样；为什么随机快排仍有最坏情况；只要求第K小与输出前K个有序元素有什么成本差别。不要给所有排序算法套用同一组稳定性和空间结论。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。