Сортировка вставками

TL;DR

Сортировка вставками (insertion sort) поддерживает отсортированный префикс массива и на каждом шаге вставляет в него очередной элемент, сдвигая бо́льшие элементы вправо. Алгоритм прост, работает на месте ([math]\displaystyle{ O(1) }[/math] памяти), устойчив и адаптивен: почти отсортированный массив сортируется за [math]\displaystyle{ O(n) }[/math], а в худшем (обратный массив) и среднем случаях — за [math]\displaystyle{ \Theta(n^2) }[/math]. Точная стоимость — [math]\displaystyle{ \Theta(n + \text{inv}) }[/math], где [math]\displaystyle{ \text{inv} }[/math] — число инверсий: сдвигов ровно [math]\displaystyle{ \text{inv} }[/math], записей вставляемого элемента [math]\displaystyle{ n-1 }[/math], итого перемещений [math]\displaystyle{ \text{inv} + (n-1) }[/math]; бинарная версия даёт [math]\displaystyle{ \Theta(n\log n) }[/math] сравнений, но сдвиги остаются [math]\displaystyle{ O(n^2) }[/math]. Благодаря простоте и дешевизне на малых отрезках вставки служат базой гибридных сортировок — introsort, mergesort, Timsort: introsort и mergesort отсекают рекурсию на 16–32 элементах, а Timsort удлиняет серии до minrun 32–64.

Свойство	Значение
Класс	Сортировка сравнением; на месте; устойчивая; онлайн
Лучший случай	[math]\displaystyle{ \Theta(n) }[/math] ([math]\displaystyle{ n-1 }[/math] сравнений и перемещений)
Средний случай	[math]\displaystyle{ \Theta(n^2) }[/math] (~[math]\displaystyle{ n^2/4 }[/math] сравнений и сдвигов)
Худший случай	[math]\displaystyle{ \Theta(n^2) }[/math] ([math]\displaystyle{ n(n-1)/2 }[/math] сравнений и сдвигов)
Сдвигов	[math]\displaystyle{ \text{inv} }[/math] (от 0 до [math]\displaystyle{ n(n-1)/2 }[/math])
Перемещений	[math]\displaystyle{ \text{inv} + (n-1) }[/math] — сдвиги плюс [math]\displaystyle{ n-1 }[/math] записей [math]\displaystyle{ v }[/math]
Память	[math]\displaystyle{ O(1) }[/math]
Устойчивость	да (строгое «>» при сдвиге)
Адаптивность	высокая, [math]\displaystyle{ \Theta(n + \text{inv}) }[/math]
Бинарная версия	[math]\displaystyle{ \Theta(n\log n) }[/math] сравнений, [math]\displaystyle{ \Theta(n^2) }[/math] перемещений в худшем
Роль	база гибридов; малые массивы; Shellsort
Родственники	обзор сортировок, Timsort, Сортировка слиянием

Определения

Сортировка вставками — алгоритм, который поочерёдно (слева направо) вставляет элемент [math]\displaystyle{ a[i] }[/math] в уже отсортированный отрезок [math]\displaystyle{ a[0..i-1] }[/math], сдвигая элементы, большие [math]\displaystyle{ a[i] }[/math], на одну позицию вправо, и кладёт [math]\displaystyle{ a[i] }[/math] на освободившееся место.

Отсортированный префикс — отрезок [math]\displaystyle{ a[0..i-1] }[/math], который поддерживается неубывающим на каждом шаге. После обработки [math]\displaystyle{ i = n-1 }[/math] (то есть при [math]\displaystyle{ i = n }[/math]) весь массив отсортирован.

Устойчивость (stability) — равные элементы сохраняют исходный порядок. Вставки устойчивы, потому что сдвигаются только элементы, строго большие вставляемого.

На месте (in-place) — используется [math]\displaystyle{ O(1) }[/math] дополнительной памяти (одна переменная под вставляемый элемент).

Онлайн-алгоритм — может сортировать данные по мере их поступления, имея отсортированными уже прочитанные элементы.

Инверсия — пара индексов [math]\displaystyle{ i \lt j }[/math] с [math]\displaystyle{ a[i] \gt a[j] }[/math]; мера «беспорядка». В сортировке вставками каждый сдвиг устраняет ровно одну инверсию.

Сдвиг — запись [math]\displaystyle{ a[j+1] \leftarrow a[j] }[/math], переносящая элемент на одну позицию вправо. Каждый сдвиг устраняет ровно одну инверсию, поэтому сдвигов ровно [math]\displaystyle{ \text{inv}(a) }[/math].

Перемещение (запись) — любая запись элемента в массив: сдвиг или запись вставляемого [math]\displaystyle{ v }[/math] на освободившееся место. Линейная версия делает [math]\displaystyle{ \text{inv}(a) + (n-1) }[/math] перемещений; у отсортированного массива это [math]\displaystyle{ n-1 }[/math], а не 0.

Бинарная сортировка вставками — вариант, в котором позиция вставки ищется двоичным поиском; в худшем случае на префиксе длины [math]\displaystyle{ i }[/math] требуется [math]\displaystyle{ \lceil\log_2(i+1)\rceil }[/math] сравнений ([math]\displaystyle{ O(\log i) }[/math] асимптотически), но перемещение элементов всё равно выполняется сдвигом.

Shellsort — обобщение: сортировка вставками по подпоследовательностям с убывающими шагами; элементы перемещаются на большие расстояния, что ускоряет последующие проходы.

Обозначения. [math]\displaystyle{ n }[/math] — длина массива; [math]\displaystyle{ i }[/math] — текущий индекс; [math]\displaystyle{ \text{inv} }[/math] — число инверсий; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Сортировка вставками — вероятно, простейший алгоритм сортировки, и у него есть три свойства, делающие его незаменимым на практике: на месте, устойчив и адаптивен. На массиве, где беспорядка мало (почти отсортированном, или «немного подправленном»), она может обгонять quicksort и mergesort, потому что делает работу, пропорциональную числу инверсий (см. рис. 2).

Идея в одном абзаце: держим префикс отсортированным. Вставляя [math]\displaystyle{ a[i] }[/math], достаточно раздвинуть часть префикса, чтобы найти место (см. рис. 1); чем меньше инверсий у [math]\displaystyle{ a[i] }[/math], тем меньше сдвигов. В пределе (массив уже отсортирован) каждый элемент вставляется на своё место за одно сравнение — суммарно [math]\displaystyle{ n-1 }[/math], то есть [math]\displaystyle{ O(n) }[/math]. Даже на уже отсортированном массиве записей [math]\displaystyle{ n-1 }[/math]: каждый элемент один раз кладётся на место, поэтому «0 сдвигов» не означает «0 перемещений».

Именно поэтому вставки используют как «хвост» рекурсивных сортировок: на коротких отрезках рекурсия и накладные расходы дороже, чем прямая вставка; а почти отсортированные данные — частая реальность.

Рис. 1. Вставка 4 в отсортированный префикс [math]\displaystyle{ [2,5,7,9] }[/math]: 5, 7, 9 сдвигаются вправо, 4 встаёт между 2 и 5; префикс снова отсортирован.

Рис. 2. Сдвигов ровно столько, сколько инверсий: у отсортированного массива 0 сдвигов, но [math]\displaystyle{ n-1 }[/math] записей; у обратного — [math]\displaystyle{ n(n-1)/2 }[/math] сдвигов. Полная стоимость — [math]\displaystyle{ \Theta(n+\text{inv}) }[/math].

Устройство

Два «указателя»: граница отсортированного префикса [math]\displaystyle{ i }[/math] и позиция [math]\displaystyle{ j }[/math] внутри префикса, идущая справа налево в поиске места. Вставляемый элемент сохраняется в переменной (это и есть дополнительная «память» [math]\displaystyle{ O(1) }[/math]), затем сдвигаются элементы.

Массив. Сдвиг — это запись элементов на соседние позиции ([math]\displaystyle{ O(n) }[/math] в худшем); обменов нет, но перемещения памяти могут быть дорогими.
Связный список. Сдвиг заменяется обновлением указателей; но поиск места остаётся линейным, поэтому общая сложность всё равно [math]\displaystyle{ O(n^2) }[/math] (см. рис. 5).

Рис. 3. Состояние массива после каждого шага: зелёный префикс отсортирован, синий элемент — вставленный на этом шаге; справа — число сдвигов.

Операции и алгоритмы

Операция: Insertion-Sort (линейный поиск места)

Идея. Для каждого [math]\displaystyle{ i }[/math] «протаскиваем» [math]\displaystyle{ a[i] }[/math] влево, пока предыдущий элемент больше.

Пошаговое описание:

Для [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n-1 }[/math]: сохранить v ← a[i], j ← i-1.
Пока j ≥ 0 и a[j] > v: сдвинуть a[j] вправо (a[j+1] ← a[j]), j ← j-1.
Положить a[j+1] ← v.

Инвариант. Перед обработкой [math]\displaystyle{ a[i] }[/math] отрезок [math]\displaystyle{ a[0..i-1] }[/math] отсортирован; элементы [math]\displaystyle{ a[i..n-1] }[/math] ещё не тронуты.

Алгоритм Insertion-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: перед шагом i отрезок a[0..i−1] отсортирован
Сложность: сдвигов ровно inv; перемещений inv + (n−1); сравнений от n−1 (лучший) до n(n−1)/2 (худший)

1  for i ← 1 to n − 1
2      v ← a[i]
3      j ← i − 1
4      while j ≥ 0 and a[j] > v          # строгое > → устойчивость
5          a[j + 1] ← a[j]
6          j ← j − 1
7      a[j + 1] ← v

Разбор. [5,2,4,6,1,3] (см. рис. 3): после шагов получаем [2,4,5,6|1,3] → [1,2,4,5,6|3] → [1,2,3,4,5,6]; всего 9 сдвигов = число инверсий, 5 записей [math]\displaystyle{ v }[/math] и [math]\displaystyle{ 9+5=14 }[/math] перемещений; сравнений — 12 (см. трассировку ниже).

Сложность. Лучший [math]\displaystyle{ \Theta(n) }[/math] — это [math]\displaystyle{ n-1 }[/math] сравнений, 0 сдвигов и [math]\displaystyle{ n-1 }[/math] перемещений; средний и худший [math]\displaystyle{ \Theta(n^2) }[/math]; память [math]\displaystyle{ O(1) }[/math].

Крайние случаи. Отсортированный массив — [math]\displaystyle{ n-1 }[/math] сравнений, 0 сдвигов и [math]\displaystyle{ n-1 }[/math] перемещений. Обратный — [math]\displaystyle{ n(n-1)/2 }[/math] сравнений и сдвигов плюс [math]\displaystyle{ n-1 }[/math] записей, итого [math]\displaystyle{ n(n-1)/2 + n-1 }[/math] перемещений. [math]\displaystyle{ n \le 1 }[/math] — ничего.

Операция: Binary-Insertion-Sort

Идея. Позицию вставки искать двоичным поиском в отсортированном префиксе (см. рис. 4).

Пошаговое описание:

Сохранить [math]\displaystyle{ v \leftarrow a[i] }[/math], lo ← 0, hi ← i.
Двоичным поиском найти верхнюю границу — первый индекс [math]\displaystyle{ p }[/math], где [math]\displaystyle{ v \lt a[p] }[/math]: пока lo < hi, взять mid ← lo + ⌊(hi − lo)/2⌋; если v < a[mid], то hi ← mid, иначе lo ← mid + 1.
Сдвинуть a[lo..i−1] на одну позицию вправо.
Положить a[lo] ← v.

Инвариант. В префиксе [math]\displaystyle{ a[0..i-1] }[/math] все элементы левее lo не больше [math]\displaystyle{ v }[/math], все начиная с hi строго больше [math]\displaystyle{ v }[/math]; позиция вставки лежит в [lo, hi]. После цикла lo = hi — первая позиция, где [math]\displaystyle{ a[p] \gt v }[/math] (верхняя граница).

Алгоритм Binary-Insertion-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован
Инвариант: позиция вставки v лежит в [lo, hi]; a[0..lo−1] ≤ v < a[hi..i−1]
Сложность: O(n log n) сравнений, но O(n²) перемещений ⇒ O(n²) времени

1  for i ← 1 to n − 1
2      v ← a[i]
3      lo ← 0 ; hi ← i                    # верхняя граница: первый p, где v < a[p]
4      while lo < hi
5          mid ← lo + ⌊(hi − lo) / 2⌋
6          if v < a[mid]: hi ← mid else lo ← mid + 1
7      for j ← i downto lo + 1
8          a[j] ← a[j − 1]               # сдвиг
9      a[lo] ← v

Разбор. Вставляем [math]\displaystyle{ v = 2 }[/math] в [math]\displaystyle{ [1,3,4,5,6,7,8,9] }[/math] (см. рис. 4):

lo=0, hi=8, mid=4, a[4]=6, [math]\displaystyle{ 2\lt 6 }[/math] → hi=4;
lo=0, hi=4, mid=2, a[2]=4, [math]\displaystyle{ 2\lt 4 }[/math] → hi=2;
lo=0, hi=2, mid=1, a[1]=3, [math]\displaystyle{ 2\lt 3 }[/math] → hi=1;
lo=0, hi=1, mid=0, a[0]=1, [math]\displaystyle{ 2\ge 1 }[/math] → lo=1.

Итог: lo = hi = 1, 4 сравнения, 7 сдвигов, 8 перемещений; линейный поиск справа делает 8 сравнений. Позиция вставки — 1.

Сложность. В худшем случае [math]\displaystyle{ \lceil\log_2(i+1)\rceil }[/math] сравнений на вставку, суммарно [math]\displaystyle{ O(n\log n) }[/math]; сдвигов [math]\displaystyle{ \text{inv} }[/math], перемещений [math]\displaystyle{ \text{inv} + (n-1) }[/math], в худшем [math]\displaystyle{ \Theta(n^2) }[/math]. На отсортированном массиве сравнений всё равно [math]\displaystyle{ \Theta(n\log n) }[/math], а линейная версия делает [math]\displaystyle{ n-1 }[/math] — бинарная теряет адаптивность по сравнениям.

Крайние случаи. lo = i — сдвигов нет, одна запись; lo = 0 — [math]\displaystyle{ i }[/math] сдвигов; дубликаты — верхняя граница сохраняет устойчивость; [math]\displaystyle{ n \le 1 }[/math] — ничего.

Рис. 4. Бинарный поиск позиции для [math]\displaystyle{ v = 2 }[/math] в [math]\displaystyle{ [1,3,4,5,6,7,8,9] }[/math]: четыре сравнения ([math]\displaystyle{ \text{mid} = 4, 2, 1, 0 }[/math]) вместо восьми при линейном поиске; сдвиги при этом остаются [math]\displaystyle{ O(n^2) }[/math].

Операция: сортировка вставками на списке

Идея. Идём по списку; каждый очередной узел вставляем в отсортированную часть, меняя указатели.

Пошаговое описание:

Обходить исходный список, сохраняя next ← cur.next.
Найти в sorted первый узел p с ключом > cur.key, запоминая prev.
Вставить cur между prev и p.
Перейти к next.

Инвариант. sorted отсортирован и содержит все обработанные узлы; необработанная часть не изменена.

Алгоритм List-Insertion-Sort(head)
Вход:  односвязный список
Выход: отсортированный список
Инвариант: sorted отсортирован и содержит все обработанные узлы
Сложность: O(n²) сравнений; обновлений указателей — O(1) на вставку

1  sorted ← NIL
2  for each узел cur в исходном порядке
3      next ← cur.next
4      вставить cur в sorted на нужное место (линейный поиск)

Разбор. [5,2,4,6,1,3] → [5] → [2,5] → [2,4,5] → [2,4,5,6] → [1,2,4,5,6] → [1,2,3,4,5,6]; всего 10 сравнений; на каждую вставку — [math]\displaystyle{ O(1) }[/math] обновлений указателей.

Сложность. [math]\displaystyle{ O(n^2) }[/math] сравнений; [math]\displaystyle{ O(1) }[/math] обновлений указателей на вставку; [math]\displaystyle{ O(1) }[/math] дополнительной памяти (указатели).

Крайние случаи. Пустой список; один узел; вставка в голову или хвост; дубликаты (вставляем после равных — устойчиво).

Рис. 5. Вставка узла 4 в отсортированную часть [math]\displaystyle{ [2,5,8] }[/math]: обновляются указатели, но поиск места остаётся линейным.

Сводная таблица сложности

Операция	Лучший	Средний	Худший	Память
Линейная: сравнения	[math]\displaystyle{ n-1 }[/math]	[math]\displaystyle{ \approx n^2/4 }[/math]	[math]\displaystyle{ n(n-1)/2 }[/math]	—
Линейная: сдвиги	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ \approx n^2/4 }[/math]	[math]\displaystyle{ n(n-1)/2 }[/math]	—
Линейная: записи [math]\displaystyle{ v }[/math]	[math]\displaystyle{ n-1 }[/math]	[math]\displaystyle{ n-1 }[/math]	[math]\displaystyle{ n-1 }[/math]	—
Линейная: перемещения	[math]\displaystyle{ n-1 }[/math]	[math]\displaystyle{ \approx n^2/4 + n-1 }[/math]	[math]\displaystyle{ n(n-1)/2 + n-1 }[/math]	—
Линейная: всего	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]
Бинарная: сравнения	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n\log n) }[/math]	—
Бинарная: сдвиги	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	—
Бинарная: перемещения	[math]\displaystyle{ n-1 }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]
Бинарная: всего	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]

Точная стоимость линейной версии: перемещения = [math]\displaystyle{ \text{inv}(a) + (n-1) }[/math], сравнения [math]\displaystyle{ \le \text{inv}(a) + (n-1) }[/math]. Для бинарной версии сравнения [math]\displaystyle{ \Theta(n\log n) }[/math] даже на отсортированном массиве; выигрыш — только при дорогих сравнениях.

Оговорка: точная оценка [math]\displaystyle{ \Theta(n+\text{inv}) }[/math] показывает адаптивность: при малом числе инверсий вставки линейны и обгоняют «быстрые» сортировки. На списке обновлений указателей [math]\displaystyle{ O(1) }[/math], но сравнений [math]\displaystyle{ O(n^2) }[/math].

Трассировка примера

a = [5, 2, 4, 6, 1, 3] (см. рис. 3).

[math]\displaystyle{ i }[/math]	Вставляем	Действие	Массив	Сравнения	Сдвиги	Перемещения
1	2	2 перед 5	`[2, 5, 4, 6, 1, 3]`	1	1	2
2	4	между 2 и 5	`[2, 4, 5, 6, 1, 3]`	2	1	2
3	6	на месте	`[2, 4, 5, 6, 1, 3]`	1	0	1
4	1	в начало	`[1, 2, 4, 5, 6, 3]`	4	4	5
5	3	между 2 и 4	`[1, 2, 3, 4, 5, 6]`	4	3	4
Всего				12	9	14

9 сдвигов = 9 инверсий; 5 записей [math]\displaystyle{ v }[/math]; [math]\displaystyle{ 14 = 9 + 5 = \text{inv} + (n-1) }[/math] перемещений; 12 сравнений [math]\displaystyle{ \le 14 }[/math].

Корректность и оценка сложности

Корректность (инвариант)

Инвариант цикла. Перед обработкой [math]\displaystyle{ a[i] }[/math] массив [math]\displaystyle{ a[0..i-1] }[/math] отсортирован; элементы [math]\displaystyle{ a[i..n-1] }[/math] не тронуты.

База. [math]\displaystyle{ i = 1 }[/math]: префикс из одного элемента [math]\displaystyle{ a[0] }[/math] отсортирован.

Сохранение. При вставке [math]\displaystyle{ v = a[i] }[/math] мы находим первую справа позицию, где a[j] ≤ v, сдвигая строго большие элементы вправо. После этого [math]\displaystyle{ a[j+1] = v }[/math], и префикс [math]\displaystyle{ a[0..i] }[/math] неубывающий: элементы слева [math]\displaystyle{ \le v }[/math] (по построению), справа были [math]\displaystyle{ \gt v }[/math] и сдвинуты. Инвариант сохранён.

Завершение. При [math]\displaystyle{ i = n-1 }[/math] (после вставки) весь массив отсортирован. [math]\displaystyle{ \square }[/math]

Устойчивость

Сдвигаются только элементы со строгим a[j] > v; равные остаются слева от [math]\displaystyle{ v }[/math] и не меняют взаимного порядка. Значит, алгоритм устойчив.

Точная стоимость

Каждый сдвиг переносит больший элемент через меньший, устраняя ровно одну инверсию; обратные операции инверсий не создают. Значит, число сдвигов равно [math]\displaystyle{ \text{inv}(a) }[/math] — числу инверсий исходного массива. Записей [math]\displaystyle{ v }[/math] ровно [math]\displaystyle{ n-1 }[/math], поэтому перемещений [math]\displaystyle{ \text{inv}(a) + (n-1) }[/math]:

[math]\displaystyle{ \text{перемещений} = \text{inv}(a) + (n - 1), \qquad \text{сравнений} \le \text{inv}(a) + (n-1). }[/math]

Отсюда: уже отсортированный массив — [math]\displaystyle{ O(n) }[/math], обратный — [math]\displaystyle{ \Theta(n^2) }[/math].

Бинарная версия

Позиция ищется за [math]\displaystyle{ \lceil\log_2(i+1)\rceil }[/math] сравнений в худшем случае на префиксе длины [math]\displaystyle{ i }[/math], суммарно [math]\displaystyle{ O(n\log n) }[/math]. Но сдвиг остаётся [math]\displaystyle{ \Theta(i) }[/math] в худшем, поэтому по времени алгоритм всё ещё [math]\displaystyle{ O(n^2) }[/math]; на отсортированном массиве сравнений [math]\displaystyle{ \Theta(n\log n) }[/math], поэтому адаптивность по сравнениям теряется. Выигрыш — только при дорогих сравнениях ключей.

Сравнение с альтернативами

Алгоритм	Средний	Лучший	Устойчив	Память	Ниша
Вставками	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	[math]\displaystyle{ O(1) }[/math]	малые, почти отсортированные
Выбором	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	нет	[math]\displaystyle{ O(1) }[/math]	мало обменов; вставки обычно лучше
Пузырьком	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	[math]\displaystyle{ O(1) }[/math]	учебный; вставки эффективнее
Слиянием	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	да	[math]\displaystyle{ O(n) }[/math]	большие [math]\displaystyle{ n }[/math], списки
Быстрая	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	нет	[math]\displaystyle{ O(\log n) }[/math]	большие [math]\displaystyle{ n }[/math], средняя скорость
Timsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	[math]\displaystyle{ O(n) }[/math]	реальные данные

Рис. 6. Шесть сортировок рядом: вставки уступают по средней асимптотике, но устойчивы, адаптивны (лучший случай [math]\displaystyle{ O(n) }[/math]) и не требуют дополнительной памяти; Timsort устойчив и в лучшем случае [math]\displaystyle{ O(n) }[/math].

Вердикт. Для больших случайных массивов вставки не годятся ([math]\displaystyle{ O(n^2) }[/math]). Их ниша — короткие отрезки (внутри гибридов) и почти отсортированные данные (см. рис. 6). Timsort устойчив и в лучшем случае [math]\displaystyle{ O(n) }[/math]; quicksort неустойчив и в лучшем случае [math]\displaystyle{ O(n\log n) }[/math]. Именно поэтому introsort, mergesort и Timsort используют вставки как «хвост» рекурсии.

Где применяется

База гибридных сортировок. introsort (std::sort) и mergesort переключаются на вставки на коротких отрезках; типичный порог отсечения — 16–32 элемента. Почему: рекурсия и накладные расходы на малых отрезках дороже прямой вставки [1][4][6].

Timsort и minrun. Timsort удлиняет короткие серии до minrun 32–64 бинарными вставками — прямое использование варианта из этой статьи [5].

Почти отсортированные данные. Обновлённые таблицы, инкрементальные вычисления, «подправленные» списки: при малом числе инверсий вставки могут оказаться самыми быстрыми — их стоимость [math]\displaystyle{ \Theta(n+\text{inv}) }[/math] [1][3].

Онлайн-вставка. Поддержание отсортированного порядка при потоке элементов; на связном списке вставка = обновление указателей [3].

Shellsort. Вставки на подпоследовательностях с убывающими шагами — практичный [math]\displaystyle{ O(n^{1.3}) }[/math]–[math]\displaystyle{ O(n^{1.5}) }[/math] алгоритм на средних массивах для удачных последовательностей шагов [2][3].

Все перечисленные ниши схематично показаны на рис. 7.

Рис. 7. Вставки как база гибридов: порог отсечения introsort/mergesort — 16–32, minrun Timsort — 32–64; почти отсортированные данные и онлайн-вставка.

Историческая справка

Сортировка вставками — одна из древнейших известных сортировок. В некоторых изложениях истории алгоритма её описание приписывают Джону Мокли (John Mauchly, 1946) ⚠️ требует проверки: первоисточник не сверен. Систематический анализ дал Дональд Кнут в The Art of Computer Programming, т. 3 (раздел 5.2.1): там же разобраны бинарный вариант, среднее число сравнений [math]\displaystyle{ \approx n^2/4 }[/math] и связь с инверсиями [2]. Простота и адаптивность обеспечили ей место в учебниках как первого алгоритма сортировки (CLRS, гл. 2) [1].

Дональд Шелл в 1959 году обобщил вставки на подпоследовательности с убывающим шагом — Shellsort, заметно ускорив алгоритм при малых накладных расходах [2][7]. Бинарный вариант (поиск позиции делением пополам) известен как binary insertion sort. В современных библиотеках вставки живут как «хвост» introsort/Timsort, где работают на коротких отрезках [4][5][6].

Типичные ошибки и подводные камни

Нестрогое сравнение (non-strict). a[j] >= v при сдвиге нарушает устойчивость; нужно строгое >.
Ошибка границ. j ≥ 0 обязательно, иначе выход за массив при вставке в начало.
Не сохранить v. Если не держать вставляемый элемент в переменной, его перезапишет сдвиг.
Ожидание [math]\displaystyle{ O(n\log n) }[/math] от бинарной версии. Сравнений меньше в худшем и среднем, но на отсортированном массиве линейная делает [math]\displaystyle{ n-1 }[/math], а бинарная — [math]\displaystyle{ \Theta(n\log n) }[/math]; перемещения в обеих версиях остаются [math]\displaystyle{ O(n^2) }[/math].
Применение к большим случайным массивам. [math]\displaystyle{ O(n^2) }[/math] катастрофичен; для больших [math]\displaystyle{ n }[/math] — гибриды.
Дорогие перемещения. Сдвиг больших структур медленный — сортировка указателей/индексов (индирекция), связный список или memmove; обмен сам по себе тоже перемещает записи.
Список вместо массива без нужды. На списке вставка дешевле по указателям, но кэш хуже; часто массив быстрее на практике.
Забыть про адаптивность. На почти отсортированных данных вставки могут обогнать quicksort — не сбрасывайте их со счетов в гибридах.
Путаница с сортировкой выбором. Выбором не адаптивна и неустойчива; вставки обычно выигрывают.
Худший вход. Обратный массив — [math]\displaystyle{ \Theta(n^2) }[/math]; в гибридах спасает не порог, а fallback: introsort переходит на heapsort при глубокой рекурсии, mergesort/Timsort — на слияние.
Переполнение mid. (lo + hi) / 2 может переполниться на больших индексах; используйте lo + (hi − lo) / 2.
Нижняя граница вместо верхней. Если искать первый элемент ≥ v, равные окажутся справа и устойчивость нарушится; нужна верхняя граница (v < a[mid]).

Задачи для практики

Базовая реализация. Реализуйте сортировку вставками и посчитайте сравнения/сдвиги. Подсказка: инвариант — отсортированный префикс.

Инверсии. Докажите, что число сдвигов равно числу инверсий; проверьте на примере. Подсказка: каждый сдвиг устраняет ровно одну инверсию.

Лучший/худший. Для [math]\displaystyle{ n = 1000 }[/math] найдите точные числа сравнений на отсортированном и обратном массивах. Подсказка: [math]\displaystyle{ n-1 }[/math] и [math]\displaystyle{ n(n-1)/2 }[/math].

Бинарная версия. Реализуйте binary insertion sort; сравните число сравнений с обычной на случайном, отсортированном и обратном массивах; объясните, почему на отсортированном бинарная проигрывает по сравнениям. Подсказка: верхняя граница для устойчивости; [math]\displaystyle{ \lceil\log_2(i+1)\rceil }[/math].

Список. Отсортируйте односвязный список вставками; оцените сравнения и обновления указателей. Подсказка: вставка между узлами.

Порог гибрида. Quicksort + вставки при [math]\displaystyle{ n \lt k }[/math]: подберите [math]\displaystyle{ k }[/math] по бенчмарку. Подсказка: 16–32 для порога отсечения; minrun Timsort 32–64 — другое.

Почти отсортировано. Дан массив с [math]\displaystyle{ \text{inv} }[/math] инверсиями; оцените время вставок как [math]\displaystyle{ \Theta(n + \text{inv}) }[/math]. Подсказка: сдвигов ровно [math]\displaystyle{ \text{inv} }[/math], записей [math]\displaystyle{ v }[/math] — [math]\displaystyle{ n-1 }[/math].

Shellsort. Реализуйте Shellsort с шагами Хиббарда и сравните с обычными вставками. Подсказка: вставки по подпоследовательностям.

Связанные темы

Сортировки — обзор алгоритмов и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
Сортировка Шелла — обобщение вставок на убывающие шаги.
Сортировка пузырьком — обменный родственник; вставки почти всегда его быстрее.
Быстрая сортировка — introsort и переключение на вставки.
Сортировка слиянием — гибрид с вставками на малых отрезках.
Timsort — бинарные вставки для удлинения runs (minrun).
Пирамидальная сортировка — другой [math]\displaystyle{ O(1) }[/math]-по-памяти алгоритм.
Асимптотическая сложность — лучший/средний/худший случаи.

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2.1 «Insertion sort» (инвариант, анализ).
Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.1 (insertion sort), §5.2.1 (Shellsort).
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts).
Musser D. R. Introspective Sorting and Selection Algorithms // Software: Practice and Experience. — 1997 (переключение на вставки в introsort).
Peters T. listsort.txt (Timsort, бинарные вставки) URL: https://github.com/python/cpython/blob/main/Objects/listsort.txt .
Wikipedia: Insertion sort. URL: https://en.wikipedia.org/wiki/Insertion_sort .
Shell D. L. A High-Speed Sorting Procedure // CACM. — 1959. — Vol. 2, № 7 .

Поиск

Навигация

Сортировка вставками

Содержание

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: Insertion-Sort (линейный поиск места)

Операция: Binary-Insertion-Sort

Операция: сортировка вставками на списке

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Корректность (инвариант)

Устойчивость

Точная стоимость

Бинарная версия

Сравнение с альтернативами

Где применяется

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Связанные темы

Источники