二分插入排序 Binary Insertion Sort
插入排序 · 折半定位 · 二分思想嫁接经典排序
普通插入慢在哪
插入排序每轮把 key 插进左边已排序的前缀：从右往左逐个比较、边比边移。可仔细想想，「找插入点」和「腾位置」是两件事——既然左边前缀已经有序，找位置根本不用一个个问过去，折半查找就行：比较次数从 O(n) 降到 O(log n)。这就是二分插入排序。
折半定位怎么走
在前缀 [0, i) 上维护搜索区间 [lo, hi)：取中点 mid，key < a[mid] 就往左半收（hi = mid）；否则往右半收（lo = mid + 1——相等也走右边，等值的新元素排到老元素后面，保持稳定）。区间一次砍一半，lo == hi 时就是插入点 pos；再把 [pos, i) 整段右移一格、key 落位。
下面固定 8 个数 [5, 2, 9, 4, 7, 1, 8, 3]。点「下一步」：看 lo（绿）/ mid（蓝）/ hi（红）三个箭头夹逼收缩定位插入点，然后玫红的 key 滑动落位。留意两轮对比——key=9 那轮定位后原位零搬移，key=1 那轮定位到 0、整段搬移 5 格：折半省的是比较，搬移一格都少不了。
第 1 轮：取出 key=2，在已排序前缀 [0,1) 里折半找插入点
1function binaryInsertionSort(a: number[]): number[] {
2 for (let i = 1; i < a.length; i++) {
3 const key = a[i];
4 let lo = 0, hi = i;
5 while (lo < hi) {
6 const mid = (lo + hi) >> 1;
7 if (key < a[mid]) {
8 hi = mid;
9 } else {
10 lo = mid + 1;
11 }
12 }
13 const pos = lo;
14 for (let k = i; k > pos; k--) {
15 a[k] = a[k - 1];
16 }
17 a[pos] = key;
18 }
19 return a;
20}
n8
i1
key2
lo-
mid-
hi-
pos-
shiftCount0
sortedUpTo1
1 / 67
复杂度：比较少了，搬移没少
比较次数 O(n log n)（每轮 log i 次），但每轮定位后的搬移仍是 O(n)——总复杂度还是 O(n²)、原地、稳定。它的价值在「比较昂贵」的场景：当比较是复杂对象/长字符串/远程调用而搬移是便宜的内存操作时，省一半以上的比较非常划算。
普通插入（插入排序页）：边比边移，比较与搬移耦合，各 O(n)。
二分插入（本页）：先折半定位（O(log n) 次比较）、再整段搬移——比较与搬移解耦。
TimSort（Python/Java 实际排序）对小段用的正是二分插入——排序线后面见。
二分插入（本页）：先折半定位（O(log n) 次比较）、再整段搬移——比较与搬移解耦。
TimSort（Python/Java 实际排序）对小段用的正是二分插入——排序线后面见。
想复习「边比边移」的原始版本，回看插入排序页对照着走一遍；「在有序区间里折半夹逼」这个动作，也正是二分查找本身——一个算法思想，两处落地。