算法概述
Timsort 是由 Tim Peters 于 2002 年为 Python 设计的混合排序算法，现已成为 Python 和 Java（Arrays.sort 对象数组）的默认排序实现。它结合了归并排序的稳定性和插入排序对小数组的高效性，通过检测输入数据中的自然有序段（Run）并执行智能合并，在部分有序数据上能达到接近 O(n) 的最优性能。
本文用 Java 完整实现 Timsort 的核心逻辑，包括 Run 检测、最小 Run 长度计算、Galloping 模式合并以及栈平衡策略。
核心原理
- Run 检测：扫描数组，识别连续递增或严格递减的子数组段（Run）。
- 递减 Run 反转：将递减 Run 原地反转，使其变为递增。
- 最小 Run 长度：对于长度为 n 的数组，最小 Run 长度 = minRun（通常为 32~64），过小的 Run 通过二分插入排序扩展。
- Run 栈管理：维护一个 Run 栈，确保栈顶三个 Run 的长度满足平衡条件（类似斐波那契序列），防止合并倾斜。
- Galloping 模式：在合并时，若某一侧连续多次胜出，则切换为二分搜索快速定位，减少比较次数。
Java 实现
import java.util.Arrays;
/**
* Timsort 自适应归并排序实现
* 时间复杂度：最坏 O(n log n)，最好 O(n)（已排序数据）
* 空间复杂度：O(n)
* 稳定性：稳定
*/
public class TimSort {
// 最小 Run 长度阈值
private static final int MIN_MERGE = 32;
// 临时数组，用于合并
private Object[] temp;
// 待排序数组
private Object[] a;
// Run 栈
private int[] runBase;
private int[] runLen;
private int stackSize = 0;
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void sort(T[] arr) {
new TimSort().sortInternal(arr);
}
@SuppressWarnings("unchecked")
private void sortInternal(Object[] arr) {
this.a = arr;
int n = arr.length;
if (n < 2) return;
// 小数组直接用二分插入排序
if (n < MIN_MERGE) {
binarySort(0, n, 0);
return;
}
// 计算最小 Run 长度
int minRun = minRunLength(n);
// 扫描并排序 Run
int lo = 0;
do {
int runLen = countRunAndMakeAscending(lo, n);
// 若 Run 长度不足 minRun，扩展至 minRun
if (runLen < minRun) {
int force = Math.min(minRun, n - lo);
binarySort(lo, lo + force, lo + runLen);
runLen = force;
}
// 将 Run 压入栈
pushRun(lo, runLen);
// 合并栈顶 Run，保持平衡
mergeCollapse();
lo += runLen;
} while (lo < n);
// 合并所有剩余 Run
mergeForceCollapse();
// 释放临时数组
this.temp = null;
this.a = null;
this.runBase = null;
this.runLen = null;
}
/**
* 计算最小 Run 长度
* 策略：将 n 分解为 2 的幂次乘以奇数，返回该奇数（或加1使其更平衡）
*/
private static int minRunLength(int n) {
int r = 0;
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
/**
* 二分插入排序：对 [lo, hi) 范围内的元素排序，
* 假设 [lo, start) 已有序
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
private void binarySort(int lo, int hi, int start) {
if (start == lo) start++;
for (; start < hi; start++) {
Comparable pivot = (Comparable) a[start];
int left = lo;
int right = start;
// 二分查找插入位置
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0) {
right = mid;
} else {
left = mid + 1;
}
}
// 将 [left, start) 后移一位，插入 pivot
int n = start - left;
System.arraycopy(a, left, a, left + 1, n);
a[left] = pivot;
}
}
/**
* 从位置 lo 开始扫描 Run，返回 Run 长度。
* 若 Run 为递减，则反转使其递增。
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
private int countRunAndMakeAscending(int lo, int hi) {
int runHi = lo + 1;
if (runHi == hi) return 1;
// 判断递增还是递减
if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) {
// 递减，继续扫描
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0) {
runHi++;
}
// 反转递减段
reverseRange(lo, runHi);
} else {
// 递增（允许相等以保证稳定性）
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0) {
runHi++;
}
}
return runHi - lo;
}
/**
* 原地反转 [lo, hi) 范围内的元素
*/
private void reverseRange(int lo, int hi) {
hi--;
while (lo < hi) {
Object t = a[lo];
a[lo++] = a[hi];
a[hi--] = t;
}
}
/**
* 将 Run 信息压入栈
*/
private void pushRun(int runBase, int runLen) {
if (this.runBase == null) {
int stackLen = 40; // 足够大的栈
this.runBase = new int[stackLen];
this.runLen = new int[stackLen];
}
this.runBase[stackSize] = runBase;
this.runLen[stackSize] = runLen;
stackSize++;
}
/**
* 合并栈顶 Run，保持平衡条件：
* runLen[i-2] > runLen[i-1] + runLen[i]
* runLen[i-1] > runLen[i]
*/
private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n - 1] <= runLen[n] + runLen[n + 1]) {
if (runLen[n - 1] < runLen[n + 1]) n--;
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} else {
break;
}
}
}
/**
* 强制合并所有剩余 Run
*/
private void mergeForceCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n - 1] < runLen[n + 1]) n--;
mergeAt(n);
}
}
/**
* 合并栈中索引 i 和 i+1 处的两个 Run
*/
@SuppressWarnings("unchecked")
private void mergeAt(int i) {
int base1 = runBase[i];
int len1 = runLen[i];
int base2 = runBase[i + 1];
int len2 = runLen[i + 1];
// 合并后更新栈
runLen[i] = len1 + len2;
if (i == stackSize - 3) {
runBase[i + 1] = runBase[i + 2];
runLen[i + 1] = runLen[i + 2];
}
stackSize--;
// 在 Run1 中二分查找 base2 首元素的插入位置
int k = gallopRight((Comparable<? super Object>) a[base2], a, base1, len1, 0);
base1 += k;
len1 -= k;
if (len1 == 0) return;
// 在 Run2 中二分查找 Run1 尾元素的插入位置
len2 = gallopLeft((Comparable<? super Object>) a[base1 + len1 - 1], a, base2, len2, len2 - 1);
if (len2 == 0) return;
// 合并两个 Run（取较小者复制到临时数组）
if (len1 <= len2) {
mergeLo(base1, len1, base2, len2);
} else {
mergeHi(base1, len1, base2, len2);
}
}
/**
* Galloping 右查找：在 sorted[lo, lo+len) 中查找 key 的插入位置
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
private static int gallopRight(Comparable key, Object[] a, int base, int len, int hint) {
int lastOfs = 0;
int ofs = 1;
if (key.compareTo(a[base + hint]) < 0) {
int maxOfs = hint + 1;
while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) < 0) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
if (ofs <= 0) ofs = maxOfs;
}
if (ofs > maxOfs) ofs = maxOfs;
int tmp = lastOfs;
lastOfs = hint - ofs;
ofs = hint - tmp;
} else {
int maxOfs = len - hint;
while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) >= 0) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
if (ofs <= 0) ofs = maxOfs;
}
if (ofs > maxOfs) ofs = maxOfs;
lastOfs += hint;
ofs += hint;
}
// 二分查找精确位置
lastOfs++;
while (lastOfs < ofs) {
int m = lastOfs + ((ofs - lastOfs) >>> 1);
if (key.compareTo(a[base + m]) < 0) {
ofs = m;
} else {
lastOfs = m + 1;
}
}
return ofs;
}
@SuppressWarnings({ "unchecked", "rawtypes" })
private static int gallopLeft(Comparable key, Object[] a, int base, int len, int hint) {
int lastOfs = 0;
int ofs = 1;
if (key.compareTo(a[base + hint]) > 0) {
int maxOfs = len - hint;
while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) > 0) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
if (ofs <= 0) ofs = maxOfs;
}
if (ofs > maxOfs) ofs = maxOfs;
lastOfs += hint;
ofs += hint;
} else {
int maxOfs = hint + 1;
while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) <= 0) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
if (ofs <= 0) ofs = maxOfs;
}
if (ofs > maxOfs) ofs = maxOfs;
int tmp = lastOfs;
lastOfs = hint - ofs;
ofs = hint - tmp;
}
lastOfs++;
while (lastOfs < ofs) {
int m = lastOfs + ((ofs - lastOfs) >>> 1);
if (key.compareTo(a[base + m]) > 0) {
lastOfs = m + 1;
} else {
ofs = m;
}
}
return ofs;
}
/**
* 合并两个 Run（Run1 较短），从左到右合并
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
private void mergeLo(int base1, int len1, int base2, int len2) {
ensureTempCapacity(len1);
System.arraycopy(a, base1, temp, 0, len1);
int cursor1 = 0;
int cursor2 = base2;
int dest = base1;
a[dest++] = a[cursor2++];
if (--len2 == 0) {
System.arraycopy(temp, cursor1, a, dest, len1);
return;
}
if (len1 == 1) {
System.arraycopy(a, cursor2, a, dest, len2);
a[dest + len2] = temp[cursor1];
return;
}
while (true) {
int count1 = 0;
int count2 = 0;
do {
if (((Comparable) a[cursor2]).compareTo(temp[cursor1]) < 0) {
a[dest++] = a[cursor2++];
count2++;
count1 = 0;
if (--len2 == 0) {
System.arraycopy(temp, cursor1, a, dest, len1);
return;
}
} else {
a[dest++] = temp[cursor1++];
count1++;
count2 = 0;
if (--len1 == 1) {
System.arraycopy(a, cursor2, a, dest, len2);
a[dest + len2] = temp[cursor1];
return;
}
}
} while ((count1 | count2) < 7); // Galloping 阈值
}
}
/**
* 合并两个 Run（Run2 较短），从右到左合并
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
private void mergeHi(int base1, int len1, int base2, int len2) {
ensureTempCapacity(len2);
System.arraycopy(a, base2, temp, 0, len2);
int cursor1 = base1 + len1 - 1;
int cursor2 = len2 - 1;
int dest = base2 + len2 - 1;
a[dest--] = a[cursor1--];
if (--len1 == 0) {
System.arraycopy(temp, 0, a, dest - (len2 - 1), len2);
return;
}
if (len2 == 1) {
dest -= len1;
cursor1 -= len1;
System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
a[dest] = temp[cursor2];
return;
}
while (true) {
int count1 = 0;
int count2 = 0;
do {
if (((Comparable) temp[cursor2]).compareTo(a[cursor1]) < 0) {
a[dest--] = a[cursor1--];
count1++;
count2 = 0;
if (--len1 == 0) {
System.arraycopy(temp, 0, a, dest - (len2 - 1), len2);
return;
}
} else {
a[dest--] = temp[cursor2--];
count2++;
count1 = 0;
if (--len2 == 1) {
dest -= len1;
cursor1 -= len1;
System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
a[dest] = temp[cursor2];
return;
}
}
} while ((count1 | count2) < 7);
}
}
private void ensureTempCapacity(int minCapacity) {
if (temp == null || temp.length < minCapacity) {
int newSize = Math.max(minCapacity, a.length >>> 1);
temp = new Object[newSize];
}
}
// ==================== 测试入口 ====================
public static void main(String[] args) {
Integer[] arr = new Integer[100000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 1000000);
}
TimSort.sort(arr);
// 验证有序性
boolean sorted = true;
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
sorted = false;
break;
}
}
System.out.println("排序结果: " + (sorted ? "正确" : "错误"));
// 测试部分有序数据
Integer[] nearly = new Integer[100000];
for (int i = 0; i < nearly.length; i++) {
nearly[i] = i + (int) (Math.random() * 10);
}
TimSort.sort(nearly);
System.out.println("部分有序排序完成");
}
}
复杂度分析
| 场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 完全随机 | O(n log n) | O(n) |
| 已排序 | O(n) | O(n) |
| 逆序 | O(n) | O(n) |
Timsort 是稳定排序，相等元素的相对顺序保持不变。
适用场景
- 对象数组排序（Java
Arrays.sort(Object[])底层实现） - 部分有序的大规模数据集
- 需要稳定排序的业务场景
- 含有连续有序子序列的日志/时间序列数据
