排序算法

1. 概述与学习目标

1.1 什么是排序算法

排序（Sorting）是计算机科学中最基础、最频繁的操作之一——将一组数据按特定顺序（升序或降序）重新排列。Donald Knuth 在 The Art of Computer Programming Vol.3《Sorting and Searching》§5 中将排序分为三大类：

1. 内部排序（§5.2 Internal Sorting）：数据全部驻留内存，包括插入类（插入、希尔）、交换类（冒泡、快排）、选择类（选择、堆排）、归并类（归并）、分布类（计数、基数、桶）；
2. 外部排序（§5.3 External Sorting）：数据量超过内存，需借助外存，核心是多路归并；
3. 多路归并（§5.4 Sorting on Large Secondary Storage Devices）：磁盘排序的工程化方案，含替换选择、多步归并。

排序算法分类树：
                              排序
                                |
        ┌───────────┬───────────┴───────────┬────────────┐
    内部排序     外部排序                分布排序          混合排序
        │           │                       │                │
   ┌────┴────┐  多路归并              ┌─────┴─────┐    ┌─────┴─────┐
  比较排序  非比较                       │           │  内省排序  Timsort
   Ω(n log n)                          │           │  (Musser 1997) (Peters 2002)
     │                                 │           │
  ┌──┴──┐                          计数排序    基数排序
  插入类 交换类                        O(n+k)     O(d(n+k))
  │     │                                │
  插入   冒泡                              └── 桶排序
  希尔   快排                                  O(n+k) 平均
        │
       堆排
       (选择类)
        │
       归并
       (归并类)

比较排序下界（Lower Bound of Comparison Sort）：任何基于比较的排序算法在最坏情况下至少需要 $\Omega(n \log n)$ 次比较。这一理论下界由决策树模型证明（详见 §3.2），意味着归并排序与堆排序已经达到了比较排序的最优。

非比较排序的突破：当元素具有特殊性质（如整数范围有限），可以绕过 $\Omega(n \log n)$ 下界实现 $O(n)$ 排序——计数排序 $O(n+k)$、基数排序 $O(d(n+k))$、桶排序 $O(n+k)$。这类算法牺牲了通用性（要求数值型或可分配的元素），换取线性时间复杂度。

一句话定义：排序 = 将数据集按序重排；比较排序下界 $\Omega(n \log n)$ 由决策树证明，归并/堆排达此下界；非比较排序利用元素性质突破至 $O(n)$；工业级实现如 Timsort、introsort 通过混合多种算法兼顾最坏与平均性能。

1.2 学习目标

完成本文档学习后，你将能够：

1. 记忆冒泡 $O(n^2)$、选择 $O(n^2)$、插入 $O(n^2)$ 平均/$O(n)$ 最优、希尔 $O(n^{1.3})$ 经验、归并 $O(n \log n)$、堆排 $O(n \log n)$、快排 $O(n \log n)$ 平均/$O(n^2)$ 最坏、计数 $O(n+k)$、基数 $O(d(n+k))$、桶 $O(n+k)$ 的形式化复杂度，复述稳定性与原地性差异；
2. 理解 von Neumann 1945 EDVAC 报告归并排序、Shell 1959 CACM 2(7):30-32 希尔排序、Hoare 1961 CACM 4(7):321 与 Computer Journal 5(1):10-15 快速排序、Williams 1964 CACM Algorithm 232 堆排序、Musser 1997 Software: Practice and Experience 27(8):983-993 内省排序、Peters 2002 Timsort 的历史脉络，说明不同排序算法的设计动机；
3. 应用冒泡（含鸡尾酒优化）、选择、插入（含二分插入）、希尔（含 Knuth/Pratt/Sedgewick 增量序列）、归并（自顶向下与自底向上）、堆排、快排（Lomuto/Hoare/三路/随机化/双轴）编写可运行的 Python/C++/Java 代码，解决 LeetCode 912 排序数组、LeetCode 215 第 K 大、LeetCode 56 合并区间、LeetCode 179 最大数、LeetCode 315 计算右侧小于当前元素的个数等问题；
4. 分析比较排序 $\Omega(n \log n)$ 下界的决策树证明（$2^h \geq n!$、Stirling 公式 $n! \approx (n/e)^n \sqrt{2\pi n}$）、快排平均 $O(n \log n)$ 的期望分析、Timsort 复杂度证明，掌握”决策树归约、期望分析、势能分析”三大核心论证方法；
5. 评估各排序算法在”小数据 vs 大数据”、“内存受限 vs 内存充裕”、“稳定 vs 不稳定”、“通用数据 vs 特殊数据”维度上的优劣，识别 Python Timsort、Java DualPivotQuicksort、C++ std::sort 内省排序、V8 Timsort 的选型动机；
6. 对比 12 种排序算法在最好/平均/最坏时间、空间、稳定性、原地性、自适应性、缓存友好性维度的差异；
7. 创造性设计基于排序的开源项目解决方案，如数据库外部归并排序、MapReduce 分布式排序、Stream 分位数估算、Top-K 流式聚合、Skew-Histogram 数据倾斜检测。

1.3 术语表

1.4 排序算法全景对比表

1.5 适用场景与不适用场景

跨模块引用：排序与查找的耦合参见 查找算法；堆排序的堆数据结构参见 堆与优先队列；分治思想的归并与快排参见 分治算法；外部排序与 MapReduce 参见 搜索算法。

2. 历史动机与演进

2.1 前排序时代：Hollerith 1890 与基数排序的起源

排序的历史远早于电子计算机。1887 年，Herman Hollerith 为美国 1890 年人口普查设计的打孔卡片制表机首次应用了基数排序思想——按卡片上不同位的孔位分桶，逐位排序即可得到整体有序结果。这次普查仅用 6 周完成（1890 年 census 比手工处理 1880 年 census 的 8 年缩短 50 倍以上），Hollerith 创立的公司即 IBM 前身。

打孔卡片排序机在 20 世纪上半叶是数据处理的标配，IBM 082 Sorter、IBM 083 Sorter 直到 1980 年代仍在使用。这一历史深刻影响了 Knuth TAOCP Vol.3 §5.2.5 对基数排序的详细论述。

2.2 von Neumann 1945：归并排序的诞生

1945 年，John von Neumann 在著名的 EDVAC 报告《First Draft of a Report on the EDVAC》中描述了归并排序——这是首个 $O(n \log n)$ 算法，比快排早 14 年。von Neumann 关注归并排序是因为它在磁带存储上自然适配（外部排序）。Knuth 在 TAOCP Vol.3 §5.2.4 详细考据了归并排序的早期历史。

归并排序的分治思想奠定了后续算法的设计范式：将问题分解为子问题，递归求解后合并。这一思想在 Strassen 矩阵乘法、Karatsuba 大数乘法、FFT 中反复出现。

2.3 Shell 1959：突破 O(n²) 的尝试

1959 年 7 月，Donald L. Shell 在 Communications of the ACM 2(7):30-32《A High-Speed Sorting Procedure》中提出希尔排序——这是首个突破 $O(n^2)$ 的排序算法。Shell 的核心洞察是：插入排序在部分有序数据上极快，故先用大步长做粗排序，再逐步减小步长做精排序，最后用步长 1 完成最终插入排序。

Shell 原始增量序列为 $\{n/2, n/4, ..., 1\}$，复杂度 $O(n^{3/2})$。后续研究者提出更优序列：

• Knuth 序列 $h_k = 3h_{k-1} + 1$（即 $1, 4, 13, 40, 121, ...$）：$O(n^{1.5})$；
• Pratt 序列（1971）：形如 $2^p 3^q$ 的所有数：$O(n \log^2 n)$；
• Sedgewick 序列（1986）：$\{1, 5, 19, 41, 109, ...\}$：$O(n^{4/3})$；
• Ciura 序列（2001）：$\{1, 4, 10, 23, 57, 132, 301, 701, 1750\}$：实测最优。

希尔排序虽已被快排、Timsort 取代，但其”递减增量”思想影响了多层索引、跳表等数据结构的设计。

2.4 Hoare 1959-1961：快速排序的诞生

1959 年，C. A. R. Hoare（Tony Hoare）在莫斯科大学访问期间开发 ALGOL 60 翻译器时发明快速排序，目的是高效翻译俄语句子到英语的词序调整。1961 年 7 月，Hoare 在 Communications of the ACM 4(7):321 发表《Algorithm 64: Quicksort》，并在 The Computer Journal 5(1):10-15 发表完整论文《Quicksort》。

快排的核心创新是分治+原地分区：选择主元 pivot，将数组分为 $\leq$ pivot 和 $>$ pivot 两部分，递归排序。平均 $O(n \log n)$ 但最坏 $O(n^2)$（当 pivot 总是选到最值时）。Hoare 1980 年因”在编程语言定义和设计方面的根本性贡献”获 Turing Award，快排是其代表性成就之一。

快排的后续优化包括：

• Sedgewick 1978 CACM 21(10):847-857《Implementing quicksort programs》：分析并优化快排实现；
• 三路快排（Dijkstra Dutch National Flag 问题）：处理大量重复键 $O(n)$；
• 随机化快排：避免最坏情况；
• Dual-Pivot Quicksort（Vladimir Yaroslavskiy 2009）：Java 7 起作为 Arrays.sort(int[]) 默认实现。

2.5 Williams 1964 与 Floyd 1964：堆排序

1964 年 6 月，J. W. J. Williams 在 Communications of the ACM 7(6):347-348《Algorithm 232: Heapsort》中提出堆排序——首个最坏 $O(n \log n)$ + 原地的排序算法。同年 12 月，Robert W. Floyd 在 CACM 7(12):701《Algorithm 245: Treesort 3》中改进建堆过程至 $O(n)$（Floyd 建堆）。

堆排序填补了快排（最坏 $O(n^2)$）与归并（需 $O(n)$ 空间）的空白。Williams 提出堆排序是为英国 Elliot Brothers 公司的磁带排序需求，堆数据结构本身成为优先队列的核心实现。

2.6 Musser 1997：内省排序

1997 年，David R. Musser 在 Software: Practice and Experience 27(8):983-993《Introspective Sorting and Selection Algorithms》中提出内省排序（introsort）。Musser 的洞察是：快排平均快但最坏 $O(n^2)$，堆排最坏 $O(n \log n)$ 但常数大、缓存差——若在快排递归过深时切换到堆排，可同时获得两者的优点。

introsort 的核心逻辑：

1. 用快排开始排序；
2. 递归深度超过 $2\log_2 n$ 时切换到堆排；
3. 子数组长度 $< 16$ 时切换到插入排序。

SGI STL 在 1997 年采纳 introsort 作为 std::sort 实现，GNU libstdc++、LLVM libc++、Microsoft STL、Boost.Sort 均沿用。introsort 是 C++ 工业级排序的事实标准。

2.7 Peters 2002：Timsort

2002 年，Tim Peters 在 Python 开发邮件列表发布 Timsort 算法，详细文档 listsort.txt 长达 70+ 页。Peters 的洞察是：真实世界的部分有序数据很常见，应主动检测并利用已有序片段（natural runs）。

Timsort 的核心流程：

1. 扫描数组检测升序/降序 run，降序 run 反转为升序；
2. run 长度 < minrun（通常 32-64）时用二分插入排序扩展；
3. 用归并栈（merge stack）维护 run，满足”栈顶三 run 长度不变式”时合并；
4. 重复直到整个数组为一个 run。

Timsort 是稳定排序，最坏 $O(n \log n)$，最好 $O(n)$（已有序数据）。自 Python 2.3（2003）起成为 list.sort 默认实现，Java 7 起作为对象排序（Arrays.sort(Object[])），Android 平台、V8 7.0+（2018）、Rust slice::sort 均采用。

2015 年，Auger-Nicaud-Pivoteau 在 arXiv:1805.04154 发现 Java 7 Timsort 实现的合并不变式有 bug，可能在特定输入下触发数组越界，Java 9 修复。这一事件印证了”实现复杂度是算法采用的隐形门槛”。

2.8 关键历史决策

timeline
    title 排序算法 70 年演进
    1887 : Hollerith 基数排序 (打孔卡片制表)
    1945 : von Neumann 归并排序 (EDVAC 报告)
    1954 : Seward 计数排序 (MIT 论文)
    1959 : Shell 希尔排序 (CACM 2(7))
    1959-1961 : Hoare 快速排序 (CACM 4(7))
    1964 : Williams 堆排序 (CACM Algorithm 232)
    1964 : Floyd 改进建堆至 O(n)
    1978 : Sedgewick 快排实现优化 (CACM 21(10))
    1993 : McIlroy 工程化基数排序 (American flag sort)
    1997 : Musser 内省排序 (Software Practice & Experience)
    2002 : Peters Timsort (Python list.sort)
    2009 : Yaroslavskiy Dual-Pivot Quicksort (Java 7)
    2015 : Auger 发现 Timsort 不变式 bug (Java 9 修复)

9 条关键设计决策：

1. 比较 vs 非比较：von Neumann 选择比较排序保证通用性；Hollerith/Seward 选择非比较排序追求线性时间；
2. 分治 vs 增量：归并与快排选择分治；插入与冒泡选择增量；
3. 递归 vs 迭代：归并与快排递归；堆排、希尔、自底向上归并迭代；
4. 稳定 vs 不稳定：归并、计数、基数稳定；快排、堆排、选择、希尔不稳定；
5. 原地 vs 辅助空间：快排、堆排、插入原地 $O(1)$；归并需 $O(n)$；
6. 平均 vs 最坏：快排平均 $O(n \log n)$ 最坏 $O(n^2)$；堆排、归并最坏 $O(n \log n)$；
7. 自适应 vs 非自适应：Timsort、插入排序对部分有序数据加速；堆排、选择排序非自适应；
8. 混合 vs 纯算法：introsort 混合快排+堆排+插入；Timsort 混合归并+二分插入；
9. 缓存友好 vs 缓存不友好：堆排缓存不友好（跨层访问）；快排、归并缓存友好（顺序访问）。

3. 形式化定义

3.1 排序问题的形式化定义

定义（排序问题）：给定 $n$ 个元素的序列 $A = [a_1, a_2, \dots, a_n]$ 与一个全序关系 $\leq$（满足自反性、反对称性、传递性），排序问题是找到一个排列 $\sigma: \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$，使得： $A[\sigma(1)] \leq A[\sigma(2)] \leq \dots \leq A[\sigma(n)]$

稳定性形式化：若 $A[i] = A[j]$ 且 $i < j$，则排序后 $\sigma^{-1}(i) < \sigma^{-1}(j)$。即相等元素的相对顺序保持不变。

比较排序的抽象：比较排序可建模为函数 compare(a, b) -> {-1, 0, 1}，仅通过该函数访问元素。任何比较排序对应一棵决策树（详见 §3.2）。

3.2 比较排序下界的决策树证明

定理（比较排序下界）：任何基于比较的排序算法在最坏情况下至少需要 $\Omega(n \log n)$ 次比较。

证明（决策树方法）：

1. 决策树模型：将比较排序的执行过程建模为一棵二叉决策树。每个内部节点表示一次比较 compare(A[i], A[j])，左子树对应 $A[i] \leq A[j]$，右子树对应 $A[i] > A[j]$。每个叶子节点对应一种输出排列。

2. 叶子数下界：$n$ 个元素共有 $n!$ 种排列。为了能输出所有可能排列，决策树至少需要 $n!$ 个叶子节点（否则某排列无法被算法产生）。

3. 高度与叶子数关系：高度为 $h$ 的二叉树最多有 $2^h$ 个叶子。故 $2^h \geq n!$，即 $h \geq \log_2(n!)$。

4. Stirling 公式： $\log_2(n!) = \sum_{k=1}^{n} \log_2 k \approx n \log_2 n - n \log_2 e + \frac{1}{2} \log_2(2\pi n) = \Theta(n \log n)$

   更精确地，Stirling 公式为 $n! \approx (n/e)^n \sqrt{2\pi n}$，故 $\log_2(n!) \approx n \log_2 n - n \log_2 e + O(\log n) = \Omega(n \log n)$。

5. 结论：决策树高度 $h \geq \log_2(n!) = \Omega(n \log n)$，即最坏情况下至少需要 $\Omega(n \log n)$ 次比较。

意义：归并排序与堆排序在最坏情况下需要 $O(n \log n)$ 次比较，达到此下界，故它们是比较排序中渐近最优的。快速排序的平均比较次数 $2(n+1)H_n - 4n \approx 1.386 n \log_2 n$（$H_n$ 为调和级数），略高于下界但常数小。

3.3 快排平均复杂度的期望分析

定理（快排平均比较次数）：随机化快排的期望比较次数为 $E[C_n] = 2(n+1)H_n - 4n = O(n \log n)$，其中 $H_n = \sum_{k=1}^{n} 1/k \approx \ln n + \gamma$（$\gamma \approx 0.5772$ 为 Euler-Mascheroni 常数）。

证明：

设 $C_n$ 为对 $n$ 个元素排序的比较次数。主元将数组分为大小 $k$ 与 $n-1-k$ 的两部分（$k$ 等概率取 $0, 1, \dots, n-1$）：

$E[C_n] = (n-1) + \frac{1}{n} \sum_{k=0}^{n-1} (E[C_k] + E[C_{n-1-k}])$

其中 $(n-1)$ 是与主元比较的次数。利用对称性：

$E[C_n] = (n-1) + \frac{2}{n} \sum_{k=0}^{n-1} E[C_k]$

两边乘 $n$： $n E[C_n] = n(n-1) + 2 \sum_{k=0}^{n-1} E[C_k]$

减去 $n-1$ 情形 $(n-1) E[C_{n-1}] = (n-1)(n-2) + 2 \sum_{k=0}^{n-2} E[C_k]$：

$n E[C_n] - (n-1) E[C_{n-1}] = n(n-1) - (n-1)(n-2) + 2 E[C_{n-1}]$ $n E[C_n] = (n-1) E[C_{n-1}] + 2(n-1) + 2 E[C_{n-1}] = (n+1) E[C_{n-1}] + 2(n-1)$

除以 $n(n+1)$： $\frac{E[C_n]}{n+1} = \frac{E[C_{n-1}]}{n} + \frac{2(n-1)}{n(n+1)}$

累加求和： $\frac{E[C_n]}{n+1} = \sum_{k=2}^{n} \frac{2(k-1)}{k(k+1)} = 2 \sum_{k=2}^{n} \left( \frac{1}{k} - \frac{1}{k+1} \right) \cdot \frac{k}{k}$

化简（关键步骤，利用 $\frac{k-1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1} - \frac{1}{k(k+1)}$ 实际上更简洁的处理）：

$\frac{E[C_n]}{n+1} = 2 \sum_{k=1}^{n} \frac{1}{k+1} - \frac{2n}{n+1} + 0 = 2 H_{n+1} - 2 - \frac{2n}{n+1}$

故： $E[C_n] = (n+1) \cdot (2 H_{n+1} - 2 - \frac{2n}{n+1}) = 2(n+1) H_n - 4n$

证毕。

渐近展开：$H_n = \ln n + \gamma + O(1/n)$，故 $E[C_n] \approx 2(n+1) \ln n \approx 2 n \ln n = 2 n \log_2 n \cdot \ln 2 \approx 1.386 n \log_2 n$。

这与下界 $n \log_2 n$ 相比仅高 $38.6\%$，是快排在工业级排序中经久不衰的核心原因。

3.4 Timsort 复杂度证明

Timsort 的复杂度分析依赖run 长度与归并栈不变式。

定义（minrun）：Timsort 设最小 run 长度为 minrun，取值范围 32-64，使 $n / \text{minrun} \approx 2^k$（或略小）。

归并栈不变式：栈顶三 run 长度 $A, B, C$（$A$ 在栈顶）需满足：

• $A > B + C$
• $B > C$

若违反任一条件则合并 $A$ 与 $B$（取较小者）。这一不变式保证栈中 run 长度呈几何级数增长，栈深度 $O(\log n)$。

定理（Timsort 复杂度）：Timsort 最坏 $O(n \log n)$，最好 $O(n)$。

证明（概要）：

• 最好情形（已有序）：扫描一次得一个长度 $n$ 的 run，无需合并，$O(n)$；
• 最坏情形：run 长度全为 minrun，栈深度 $O(n/\text{minrun}) = O(n/32)$，每层归并代价 $O(n)$，总复杂度 $O(n \log n)$。

更精细的分析（Auger et al. 2015）证明 Timsort 最坏比较次数上界为 $n \log_2 n - n \log_2 \phi + O(n)$（$\phi = (1+\sqrt{5})/2$），略优于归并排序的 $n \log_2 n - n + O(1)$。

3.5 稳定性的形式化保证

定义（稳定排序）：排序算法 $\mathcal{A}$ 是稳定的，当且仅当对任意输入 $A$ 与任意相等对 $A[i] = A[j]$（$i < j$），$\mathcal{A}(A)$ 输出中 $\sigma^{-1}(i) < \sigma^{-1}(j)$。

稳定性的工程价值：

1. 多关键字排序：先按次要关键字排序，再按主要关键字稳定排序，即可实现多关键字排序；
2. 数据库 ORDER BY：SQL 标准要求 ORDER BY 稳定（虽然 SQL 标准未显式规定，但工业实现均稳定）；
3. UI 列表排序：用户先按时间排序再按作者排序，期望保留时间顺序的稳定性。

各排序的稳定性分析：

• 冒泡、插入、归并、计数、基数、桶：稳定（实现正确时）；
• 选择、希尔、快排、堆排：不稳定（存在反例）。

选择排序不稳定的反例：$[5_a, 5_b, 2]$，第一轮选 $2$ 与 $5_a$ 交换得 $[2, 5_b, 5_a]$，破坏了 $5_a$ 与 $5_b$ 的相对顺序。

快排不稳定的反例：$[3_a, 2, 3_b, 1]$，以 $3_a$ 为主元，分区后 $3_b$ 可能被换到 $3_a$ 之前。

4. 冒泡排序

4.1 算法描述

冒泡排序（Bubble Sort）通过反复遍历数组，比较相邻元素并在逆序时交换，使大元素逐步”冒泡”到末尾。每轮遍历将当前未排序部分的最大值推到正确位置。

初始: [5, 3, 8, 1, 2]
第1轮: [3, 5, 1, 2, 8] -- 8 冒泡到末尾
第2轮: [3, 1, 2, 5, 8] -- 5 冒泡到倒数第二
第3轮: [1, 2, 3, 5, 8] -- 3 冒泡到倒数第三
第4轮: [1, 2, 3, 5, 8] -- 无交换，提前终止

4.2 Python 实现

from typing import List


def bubble_sort(arr: List[int]) -> List[int]:
    """
    冒泡排序（含提前终止优化）
    
    Args:
        arr: 待排序数组
        
    Returns:
        排序后的数组（原地修改）
        
    Time:  最好 O(n)，平均 O(n^2)，最坏 O(n^2)
    Space: O(1)
    Stable: True
    """
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        # 每轮将最大元素冒泡到 n-1-i 位置
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 若某轮无交换，说明数组已有序
        if not swapped:
            break
    return arr


def cocktail_sort(arr: List[int]) -> List[int]:
    """
    鸡尾酒排序（双向冒泡）
    
    交替从左到右和从右到左遍历，加速处理"乌龟"（尾部小值）问题。
    
    Args:
        arr: 待排序数组
        
    Returns:
        排序后的数组
        
    Time:  最好 O(n)，平均 O(n^2)，最坏 O(n^2)
    Space: O(1)
    Stable: True
    """
    n = len(arr)
    left, right = 0, n - 1
    while left < right:
        swapped = False
        # 从左到右，将最大值冒泡到 right
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        right -= 1
        # 从右到左，将最小值冒泡到 left
        for i in range(right, left, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True
        left += 1
        if not swapped:
            break
    return arr

4.3 C++ 实现

#include <vector>
#include <utility>

// 冒泡排序（含提前终止）
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

4.4 Java 实现

public class BubbleSort {
    
    /**
     * 冒泡排序（含提前终止）
     * @param arr 待排序数组
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

4.5 复杂度分析

空间 $O(1)$，稳定，原地，自适应（带提前终止优化）。

4.6 工程价值与局限

冒泡排序在实际工程中几乎不使用，原因：

1. 平均 $O(n^2)$ 慢于插入排序（常数更大）；
2. 交换次数与比较次数相等，对大元素（结构体）效率差；
3. CPU 缓存利用差（频繁相邻访问，但每次访问都触发比较+交换）。

教学价值：冒泡排序是入门排序的最佳教学算法，因其简单性揭示了排序的核心要素：比较、交换、循环不变式。

5. 选择排序与插入排序

5.1 选择排序

算法：每轮选出剩余元素中的最小值放到已排序末尾。

def selection_sort(arr: list[int]) -> list[int]:
    """
    选择排序
    
    Time:  最好/平均/最坏 O(n^2)
    Space: O(1)
    Stable: False
    """
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

特点：

• 比较次数固定 $n(n-1)/2$，交换次数最多 $n-1$ 次；
• 不稳定（如 $[5_a, 5_b, 2]$，$5_a$ 与 $2$ 交换破坏 $5_a, 5_b$ 顺序）；
• 非自适应（无论输入如何都执行相同次数）；
• 适合指针排序：当元素较大但指针小时，交换指针比交换元素高效。

5.2 插入排序

算法：模拟扑克牌整理过程，将新牌插入已排好的手牌中。

def insertion_sort(arr: list[int]) -> list[int]:
    """
    插入排序
    
    Time:  最好 O(n)，平均 O(n^2)，最坏 O(n^2)
    Space: O(1)
    Stable: True
    Adaptive: True
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 将 key 插入到 arr[0..i-1] 的正确位置
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


def binary_insertion_sort(arr: list[int]) -> list[int]:
    """
    二分插入排序
    
    用二分查找确定插入位置，比较次数 O(n log n)，但移动次数仍 O(n^2)。
    
    Time:  最好 O(n)，平均 O(n^2)，最坏 O(n^2)
    Space: O(1)
    Stable: True
    """
    for i in range(1, len(arr)):
        key = arr[i]
        # 二分查找插入位置
        left, right = 0, i
        while left < right:
            mid = (left + right) // 2
            if arr[mid] <= key:
                left = mid + 1
            else:
                right = mid
        # 将 arr[left..i-1] 右移一位
        for j in range(i, left, -1):
            arr[j] = arr[j - 1]
        arr[left] = key
    return arr

特点：

• 最好 $O(n)$：已有序时每轮仅比较一次；
• 平均 $O(n^2)$：约 $n^2/4$ 次比较与移动；
• 稳定、原地、自适应；
• 小数据最优：$n < 50$ 时通常优于快排（常数小，无递归开销）；
• Timsort 与 introsort 的小数据回退方案。

为什么二分插入排序仍 $O(n^2)$？ 虽然二分查找将比较次数降到 $O(\log i)$，但元素移动仍需 $O(i)$ 次（数组连续存储特性）。二分插入排序在元素较大、比较成本高的场景（如字符串）有优势。

6. 希尔排序

6.1 算法描述

希尔排序（Shell Sort）通过递减增量分组插入排序：先用大步长做粗排序，再逐步减小步长做精排序，最后用步长 1 完成最终插入排序。这突破了 $O(n^2)$ 的限制，因为大步长阶段将远距离元素快速归位，使后续小步长插入排序面对的是”近似有序”数据，而插入排序在近似有序数据上接近 $O(n)$。

增量序列 {5, 3, 1}，数组 [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10]

gap=5 分组（5 个子序列）：
  13 25 45 10  -> 10 13 25 45
  14 59 27     -> 14 27 59
  94 94 73     -> 73 94 94
  33 65 25     -> 25 33 65
  82 23 39     -> 23 39 82
  合并后: [10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45]

gap=3 分组（3 个子序列），各组插入排序
gap=1 最终插入排序

6.2 Python 实现

def shell_sort(arr: list[int], gaps: str = "ciura") -> list[int]:
    """
    希尔排序
    
    Args:
        arr: 待排序数组
        gaps: 增量序列名，可选 "shell" "knuth" "sedgewick" "ciura"
        
    Returns:
        排序后的数组
        
    Time:  依赖增量序列，Ciura 实测最快约 O(n^{1.3})
    Space: O(1)
    Stable: False
    """
    n = len(arr)
    gap_sequences = {
        "shell":     [n // 2, n // 4, ..., 1],  # 原始版本，O(n^{3/2})
        "knuth":     [1, 4, 13, 40, 121, 364, 1093, ...],  # 3h+1
        "sedgewick": [1, 5, 19, 41, 109, 209, 505, 929, 2161, ...],
        "ciura":     [1, 4, 10, 23, 57, 132, 301, 701, 1750],  # 实测最优
    }
    
    if gaps == "shell":
        gap_list = []
        g = n // 2
        while g > 0:
            gap_list.append(g)
            g //= 2
    elif gaps == "knuth":
        gap_list = []
        g = 1
        while g < n:
            gap_list.append(g)
            g = 3 * g + 1
        gap_list.reverse()
    elif gaps == "sedgewick":
        gap_list = []
        k = 0
        while True:
            # Sedgewick 1986: 4^k + 3*2^(k-1) + 1
            if k == 0:
                g = 1
            else:
                g = 4 ** k + 3 * 2 ** (k - 1) + 1
            if g >= n:
                break
            gap_list.append(g)
            k += 1
        gap_list.reverse()
    else:  # ciura
        gap_list = [g for g in [1750, 701, 301, 132, 57, 23, 10, 4, 1] if g < n]
        if not gap_list:
            gap_list = [1]
    
    for gap in gap_list:
        # 对每个子序列做插入排序
        for i in range(gap, n):
            key = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > key:
                arr[j + gap] = arr[j]
                j -= gap
            arr[j + gap] = key
    return arr

6.3 增量序列与复杂度

希尔排序不稳定：相同元素可能因步长分组跨越彼此，破坏相对顺序。

工程地位：希尔排序因实现简单、原地、$O(n^{1.3})$ 在嵌入式系统、低开销场景仍被使用。Linux kernel lib/sort.c 在 2017 年前使用希尔排序（后改用 introsort 变体）。

7. 归并排序

7.1 算法描述

归并排序（Merge Sort）由 von Neumann 1945 年发明，是首个 $O(n \log n)$ 排序算法。核心思想是分治：将数组对半分，递归排序后合并两个有序子数组。

[38, 27, 43, 3, 9, 82, 10]
        分治
[38, 27, 43, 3] [9, 82, 10]
[38, 27] [43, 3] [9, 82] [10]
[38] [27] [43] [3] [9] [82] [10]
        合并
[27, 38] [3, 43] [9, 82] [10]
[3, 27, 38, 43] [9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]

7.2 Python 实现

from typing import List


def merge_sort_topdown(arr: List[int]) -> List[int]:
    """
    自顶向下归并排序（递归版）
    
    Time:  O(n log n)
    Space: O(n)
    Stable: True
    """
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_topdown(arr[:mid])
    right = merge_sort_topdown(arr[mid:])
    return _merge(left, right)


def _merge(left: List[int], right: List[int]) -> List[int]:
    """合并两个有序数组"""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        # 注意：用 <= 保证稳定性（相等时取 left）
        if left[i] <= 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


def merge_sort_bottomup(arr: List[int]) -> List[int]:
    """
    自底向上归并排序（迭代版）
    
    自底向上消除递归，避免栈溢出。
    
    Time:  O(n log n)
    Space: O(n)
    Stable: True
    """
    n = len(arr)
    if n <= 1:
        return arr
    width = 1
    while width < n:
        # 以 width 为单位两两合并
        for i in range(0, n, 2 * width):
            left = arr[i:i + width]
            right = arr[i + width:i + 2 * width]
            arr[i:i + 2 * width] = _merge(left, right)
        width *= 2
    return arr

7.3 C++ 实现

#include <vector>

void mergeSortHelper(std::vector<int>& arr, std::vector<int>& tmp,
                     int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSortHelper(arr, tmp, left, mid);
    mergeSortHelper(arr, tmp, mid + 1, right);
    
    // 合并 arr[left..mid] 与 arr[mid+1..right]
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    for (int p = left; p <= right; ++p) arr[p] = tmp[p];
}

void mergeSort(std::vector<int>& arr) {
    if (arr.size() <= 1) return;
    std::vector<int> tmp(arr.size());
    mergeSortHelper(arr, tmp, 0, arr.size() - 1);
}

7.4 复杂度分析

递推式：$T(n) = 2T(n/2) + O(n)$，由主定理（case 2）得 $T(n) = O(n \log n)$。

空间：$O(n)$（合并时需要辅助数组）。

比较次数：最坏 $n \log_2 n - n + 1$，最少 $n \log_2 n / 2$（已部分有序时）。

稳定性：稳定（合并时相等元素取左路）。

7.5 工程应用

1. Java Arrays.sort(Object[])（Java 7 前）：纯归并排序；
2. Python Timsort 的合并阶段：检测自然 run 后归并；
3. 数据库外部排序：多路归并 + 替换选择；
4. MapReduce shuffle：分布式归并排序；
5. 链表排序：归并是链表的最佳排序方法（无随机访问，但合并 $O(1)$ 空间）。

8. 堆排序

8.1 算法描述

堆排序（Heapsort）由 Williams 1964 年发明，是首个最坏 $O(n \log n)$ + 原地的排序。算法分两步：

1. 建堆：用 Floyd 自底向上建堆法 $O(n)$ 构造最大堆；
2. 排序：反复取出堆顶（最大值）放到末尾，缩小堆，再下沉调整。

详见 堆与优先队列 章节。

8.2 Python 实现

def heap_sort(arr: list[int]) -> list[int]:
    """
    堆排序
    
    Time:  O(n log n) 最坏保证
    Space: O(1)
    Stable: False
    """
    n = len(arr)
    
    def sift_down(start: int, end: int) -> None:
        """在 arr[start..end] 范围内下沉根节点"""
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            # 选较大子节点
            if child + 1 <= end and arr[child + 1] > arr[child]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break
    
    # Phase 1: Floyd 自底向上建堆 O(n)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n - 1)
    
    # Phase 2: 反复取出堆顶放到末尾
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(0, i - 1)
    
    return arr

8.3 复杂度分析

建堆复杂度（Floyd 1964）：$\sum_{h=0}^{\lfloor \log n \rfloor} \lceil n/2^{h+1} \rceil \cdot h \leq 2n = O(n)$。

排序阶段：$n-1$ 次下沉，每次 $O(\log n)$，共 $O(n \log n)$。

总复杂度：$O(n) + O(n \log n) = O(n \log n)$。

空间：$O(1)$（原地）。

稳定性：不稳定（父子节点交换可能跨过相等元素）。

缓存不友好：堆访问跨层（索引 $i \to 2i+1$），跳跃大，cache miss 频繁。这是堆排序实测比快排、归并慢 2-5 倍的核心原因。

8.4 工程应用

1. introsort 的回退方案：快排递归过深时切换到堆排；
2. 嵌入式系统：$O(1)$ 空间、最坏 $O(n \log n)$，适合资源受限场景；
3. Top-K 问题：建堆后取前 $k$ 个，$O(n + k \log n)$；
4. Linux kernel lib/sort.c：早期希尔排序，2017 年后改用 introsort 变体。

9. 快速排序

9.1 算法描述

快速排序（Quicksort）由 Hoare 1959-1961 年发明，平均 $O(n \log n)$ 但最坏 $O(n^2)$，因常数小、缓存友好，是工业级排序的核心。算法分三步：

1. 选主元（pivot）：从数组中选一个元素作为分区基准；
2. 分区（partition）：将 $\leq$ pivot 的放左，$>$ pivot 的放右；
3. 递归：对左右两部分递归排序。

9.2 分区方案

9.2.1 Lomuto 分区（最简方案）

def partition_lomuto(arr: list[int], low: int, high: int) -> int:
    """
    Lomuto 分区：选最右元素为主元
    
    简单但性能差：当数组已有序时每次分区不平衡，最坏 O(n^2)。
    """
    pivot = arr[high]
    i = low - 1  # i 指向 "<= pivot" 区域的最后一个元素
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quicksort_lomuto(arr: list[int], low: int, high: int) -> None:
    if low < high:
        p = partition_lomuto(arr, low, high)
        quicksort_lomuto(arr, low, p - 1)
        quicksort_lomuto(arr, p + 1, high)

9.2.2 Hoare 分区（原始版本，性能更优）

def partition_hoare(arr: list[int], low: int, high: int) -> int:
    """
    Hoare 分区：选最左元素为主元，双向扫描
    
    比 Lomuto 平均少 3 倍交换次数。
    """
    pivot = arr[low]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]


def quicksort_hoare(arr: list[int], low: int, high: int) -> None:
    if low < high:
        p = partition_hoare(arr, low, high)
        quicksort_hoare(arr, low, p)
        quicksort_hoare(arr, p + 1, high)

9.2.3 三路快排（处理大量重复键）

def partition_three_way(arr: list[int], low: int, high: int) -> tuple[int, int]:
    """
    三路分区（Dijkstra Dutch National Flag）
    
    将数组分为三部分：< pivot | == pivot | > pivot
    适合大量重复键场景，O(n) 最优。
    """
    pivot = arr[low]
    lt = low      # lt 之前是 < pivot
    gt = high     # gt 之后是 > pivot
    i = low + 1
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    return lt, gt


def quicksort_three_way(arr: list[int], low: int, high: int) -> None:
    if low < high:
        lt, gt = partition_three_way(arr, low, high)
        quicksort_three_way(arr, low, lt - 1)
        quicksort_three_way(arr, gt + 1, high)

9.2.4 随机化快排

import random


def quicksort_randomized(arr: list[int], low: int, high: int) -> None:
    """
    随机化快排：随机选主元，避免最坏情况
    
    期望复杂度 O(n log n)，且不依赖输入分布。
    """
    if low < high:
        # 随机选主元并交换到 high
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
        p = partition_lomuto(arr, low, high)
        quicksort_randomized(arr, low, p - 1)
        quicksort_randomized(arr, p + 1, high)

9.3 主元选择策略

9.4 工程实现技巧

1. 小数据切到插入排序：当 high - low < 16 时改用插入排序（常数小，无递归开销）；
2. 尾递归消除：递归调用时先递归较小一侧，较大一侧改为循环，最坏栈深 $O(\log n)$；
3. 三数取中：避免有序输入退化；
4. partition 后立即检查已有序：若一侧长度为 0，跳过递归。

9.5 复杂度分析

• 最好 $O(n \log n)$（主元每次都居中）；
• 平均 $O(n \log n)$（期望 $1.386 n \log_2 n$ 次比较）；
• 最坏 $O(n^2)$（主元每次都是极值，如已有序数组）；
• 空间 $O(\log n)$（递归栈，尾递归优化后）；
• 不稳定。

9.6 Dual-Pivot Quicksort（Java 7+）

Vladimir Yaroslavskiy 2009 年提出双主元快排，将数组分为三部分（$< P_1$、$P_1 \leq x \leq P_2$、$> P_2$）。Java 7 起作为 Arrays.sort(int[])、Arrays.sort(long[]) 等基础类型排序的默认实现。

Wild-Nebel 2012 证明 Dual-Pivot Quicksort 平均比较次数 $\frac{2}{5} n \ln n \approx 0.277 n \log_2 n$，优于单主元快排的 $1.386 n \log_2 n / 2 = 0.693 n \log_2 n$。

10. 非比较排序：计数、基数、桶

10.1 计数排序

算法：统计每个元素出现次数，按值域累加输出。

def counting_sort(arr: list[int], max_val: int = None) -> list[int]:
    """
    计数排序
    
    Args:
        arr: 待排序数组（非负整数）
        max_val: 元素最大值，默认从 arr 推断
        
    Time:  O(n + k)，k 为值域大小
    Space: O(k)
    Stable: True（按累加计数反向填充）
    """
    if not arr:
        return arr
    if max_val is None:
        max_val = max(arr)
    
    # 统计每个值出现次数
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    
    # 累加（确定每个值的结束位置）
    for i in range(1, max_val + 1):
        count[i] += count[i - 1]
    
    # 反向填充保证稳定性
    result = [0] * len(arr)
    for x in reversed(arr):
        count[x] -= 1
        result[count[x]] = x
    
    return result

应用：

• 年龄排序（值域 0-150）；
• 字符 ASCII 排序（值域 0-127）；
• 基数排序的子过程。

10.2 基数排序

算法：从低位到高位（LSD）或从高位到低位（MSD）按位排序，每位用计数排序。

def radix_sort_lsd(arr: list[int]) -> list[int]:
    """
    LSD 基数排序（从最低位到最高位）
    
    Time:  O(d(n+k))，d 为位数，k 为基数
    Space: O(n+k)
    Stable: True
    """
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = _counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr


def _counting_sort_by_digit(arr: list[int], exp: int) -> list[int]:
    """按某一位做计数排序"""
    n = len(arr)
    count = [0] * 10
    output = [0] * n
    
    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
    
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # 反向填充保证稳定性
    for x in reversed(arr):
        digit = (x // exp) % 10
        count[digit] -= 1
        output[count[digit]] = x
    
    return output


def radix_sort_msd(arr: list[str], digit: int = 0) -> list[str]:
    """
    MSD 基数排序（从最高位到最低位，用于字符串）
    
    适合变长字符串排序。
    """
    if len(arr) <= 1:
        return arr
    
    buckets = [[] for _ in range(256)]
    finished = []
    for s in arr:
        if digit < len(s):
            buckets[ord(s[digit])].append(s)
        else:
            finished.append(s)
    
    result = finished
    for b in buckets:
        if b:
            result.extend(radix_sort_msd(b, digit + 1))
    return result

应用：

• 手机号排序（11 位定长数字串）；
• IP 地址排序；
• 字符串字典排序（MSD）；
• 美国 1890 年人口普查（Hollerith 打孔卡片）。

10.3 桶排序

算法：将元素按值域均匀分到 $k$ 个桶，每桶内排序后合并。

def bucket_sort(arr: list[float], bucket_count: int = 10) -> list[float]:
    """
    桶排序
    
    Args:
        arr: 待排序数组（浮点数 [0, 1)）
        bucket_count: 桶数
        
    Time:  平均 O(n+k)，最坏 O(n^2)（所有元素入同桶）
    Space: O(n+k)
    Stable: True（若桶内排序稳定）
    """
    if not arr:
        return arr
    
    buckets = [[] for _ in range(bucket_count)]
    for x in arr:
        idx = min(int(x * bucket_count), bucket_count - 1)
        buckets[idx].append(x)
    
    for b in buckets:
        b.sort()  # 桶内排序（用稳定排序）
    
    result = []
    for b in buckets:
        result.extend(b)
    return result

应用：

• 均匀分布的浮点数排序（如随机数）；
• 直方图统计；
• 大数据预处理分桶。

11. 工业级混合排序

11.1 内省排序（introsort）

算法（Musser 1997）：

1. 用快排开始排序（三数取中选主元）；
2. 递归深度超过 $2 \log_2 n$ 时切换到堆排（避免快排最坏 $O(n^2)$）；
3. 子数组长度 $< 16$ 时切换到插入排序（小数据常数小）。

实现：

import math


def introsort(arr: list[int]) -> list[int]:
    """
    内省排序（introsort）
    
    Musser 1997，C++ std::sort 的核心实现。
    
    Time:  O(n log n) 最坏保证
    Space: O(log n)
    Stable: False
    """
    max_depth = 2 * int(math.log2(len(arr))) if arr else 0
    _introsort_helper(arr, 0, len(arr) - 1, max_depth)
    # 最后做一次插入排序清理小段
    _insertion_sort_range(arr, 0, len(arr) - 1)
    return arr


def _introsort_helper(arr: list[int], low: int, high: int, depth: int) -> None:
    while high - low > 16:
        if depth == 0:
            # 切换到堆排
            _heapsort_range(arr, low, high)
            return
        depth -= 1
        p = _partition_median_three(arr, low, high)
        _introsort_helper(arr, low, p - 1, depth)
        low = p + 1  # 尾递归优化


def _partition_median_three(arr: list[int], low: int, high: int) -> int:
    """三数取中选主元"""
    mid = low + (high - low) // 2
    # 排序 arr[low], arr[mid], arr[high]，取中位数到 high-1
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    # 主元放到 high
    arr[mid], arr[high] = arr[high], arr[mid]
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def _heapsort_range(arr: list[int], low: int, high: int) -> None:
    """对 arr[low..high] 做堆排"""
    n = high - low + 1
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, low, i, n)
    for i in range(n - 1, 0, -1):
        arr[low], arr[low + i] = arr[low + i], arr[low]
        _sift_down(arr, low, 0, i)


def _sift_down(arr: list[int], base: int, start: int, size: int) -> None:
    root = start
    while True:
        child = 2 * root + 1
        if child >= size:
            break
        if child + 1 < size and arr[base + child + 1] > arr[base + child]:
            child += 1
        if arr[base + root] < arr[base + child]:
            arr[base + root], arr[base + child] = arr[base + child], arr[base + root]
            root = child
        else:
            break


def _insertion_sort_range(arr: list[int], low: int, high: int) -> None:
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key