Insertion Sort

Проблема

Представьте, что вы держите в руке карты и сортируете их по одной, вставляя каждую новую карту в нужное место среди уже отсортированных. Нужен алгоритм, который так же естественно работает с данными, поступающими по одному элементу (например, поток), и который особенно эффективен, если данные уже почти упорядочены.

Решение

Массив делится на отсортированную часть слева (изначально из одного элемента) и неотсортированную часть справа. На каждом шаге берётся первый элемент неотсортированной части и сдвигается влево через отсортированную часть до тех пор, пока не найдётся элемент меньше него - туда он и вставляется. Отсортированная часть растёт на один элемент за шаг.

Как это работает

Сортировка вставками строит отсортированную часть постепенно, беря по одному элементу из неотсортированного хвоста и находя ему место сдвигом (не обменом) уже упорядоченных соседей. Это отличает её от алгоритмов на основе swap - здесь двигается блок элементов, а не пара.

На конкретных числах: массив [5, 2, 4, 6, 1, 3]. При i = 1 ключ current = 2; 5 > 2, поэтому 5 сдвигается вправо → [5, 5, 4, 6, 1, 3], j доходит до -1, ключ встаёт в начало → [2, 5, 4, 6, 1, 3]. При i = 2 ключ current = 4; 5 > 4 - сдвиг → [2, 5, 5, 6, 1, 3]; 2 > 4 ложно - остановка, ключ встаёт на позицию 1 → [2, 4, 5, 6, 1, 3]. За два шага понадобилось всего 2 сдвига.

Отличительная черта алгоритма - адаптивность к исходному порядку. На почти отсортированном массиве каждый ключ уже стоит рядом со своей финальной позицией, поэтому цикл while останавливается почти сразу же после первого сравнения, и общее число сдвигов близко к нулю.

На обратно отсортированном массиве происходит противоположное. Для [6, 5, 4, 3, 2, 1] (n = 6): при i = 1 ключ 5 требует 1 сдвиг, при i = 2 ключ 4 - 2 сдвига, ..., при i = 5 ключ 1 - 5 сдвигов. Сумма 1 + 2 + 3 + 4 + 5 = 15 сдвигов - это худший случай алгоритма.

Эта цифра не случайна - число сдвигов для каждого элемента равно числу элементов слева от него, которые больше него самого, то есть числу инверсий, в которых он участвует. Сумма по всем элементам даёт полное число инверсий массива: для [6, 5, 4, 3, 2, 1] это ровно n(n-1)/2 = 6·5/2 = 15 - максимально возможное число инверсий для n = 6, совпадающее со счётом выше.

Механика сдвига отличается от обмена и по паттерну доступа к памяти. Swap в bubble/selection sort - это перестановка ровно двух ячеек. Сдвиг в insertion sort - это последовательное копирование блока a[j] в a[j+1] при движении j влево, а затем одна финальная запись ключа. При коротких сдвигах (что типично на почти отсортированных данных) это дёшево; при длинных сдвигах (худший случай) число записей растёт линейно с длиной сдвигаемого блока.

В сравнении с Bubble Sort оба алгоритма делают O(n²) сравнений в худшем случае, но по-разному распределяют работу за проход: bubble sort двигает каждый большой элемент только на одну позицию за проход, insertion sort сразу дотаскивает вставляемый ключ до правильного места за один внутренний цикл. Итоговая асимптотика совпадает, но константы и характер деградации на разных входах отличаются - именно поэтому insertion sort, а не bubble sort, оказался финальным шагом Timsort.

Нюансы выбора

Против Selection Sort - на почти отсортированных данных вставками выигрывают, потому что адаптируются к числу инверсий (см. пример выше: 15 сдвигов на n = 6 в худшем случае), тогда как Selection Sort всегда делает ровно n-1 перестановку, сколько бы элементов уже ни стояло на своих местах.

Онлайн-сценарий - когда элементы поступают по одному и отсортированный порядок нужен в любой промежуточный момент, а не только в конце. Selection Sort для этого не годится - ей нужно видеть весь оставшийся диапазон, чтобы найти минимум.

Малые подмассивы внутри гибридных сортировок - Timsort переключается на (бинарную) сортировку вставками для «прогонов» короче примерно 32-64 элементов, Introsort в C++ STL - на финальном проходе после рекурсивного деления. Причина одна и та же: у insertion sort ниже константы на маленьком n, чем у merge/quicksort с их накладными расходами на рекурсию и слияние.

На связных списках, а не массивах - вставка узла в найденную позицию стоит O(1) (переставить пару указателей), поэтому оверхед сдвига, характерный именно для непрерывного массива в памяти, вообще исчезает - остаётся только O(n) на поиск позиции.

Не выбирать для больших случайных массивов - без знания о порядке входных данных O(n²) сдвигов делает алгоритм заметно медленнее Merge Sort, Quicksort или Heap Sort уже на нескольких тысячах элементов; для этого случая нужен алгоритм с гарантией O(n log n), а не адаптивностью.

Примеры в коде

Timsort (Tim Peters, 2002) - стандартный алгоритм сортировки в CPython (listobject.c) и Java (ComparableTimSort для объектов) - использует именно бинарную сортировку вставками для «прогонов» короче MIN_RUN (обычно 32-64 элемента), находя позицию вставки бинарным поиском перед сдвигом.

`java.util.DualPivotQuicksort` (примитивные массивы Java, не объекты) переключается с quicksort на insertion sort для поддиапазонов короче константы INSERTION_SORT_THRESHOLD = 47 - число подобрано эмпирически по бенчмаркам JDK.

GCC libstdc++ `std::sort` реализует Introsort и завершает его отдельным проходом __final_insertion_sort с порогом в 16 элементов - на этом этапе массив уже «почти отсортирован» (каждый элемент рекурсией уже подведён близко к финальной позиции), что именно та ситуация, в которой вставками наиболее эффективны.

Прошивки микроконтроллеров без динамической памяти используют сортировку вставками там, где данных мало (десятки записей), а O(1) дополнительной памяти и отсутствие рекурсии важнее асимптотики - лишний стек вызовов quicksort в среде с несколькими килобайтами ОЗУ может быть недопустим.

Учебные визуализаторы алгоритмов (например, VisuAlgo) почти всегда ставят insertion sort рядом с selection sort именно для демонстрации адаптивности: на одном и том же почти отсортированном входе insertion sort делает заметно меньше операций, а selection sort - нет.

Когда применять

• Когда данные почти отсортированы или поступают потоком, элемент за элементом.
• Как финальный проход для маленьких подмассивов внутри более сложных алгоритмов (Timsort, интроспективная сортировка).

Примеры из практики

• Timsort (используется в Python sorted() и Java Arrays.sort() для объектов) применяет сортировку вставками для небольших «прогонов» перед их слиянием.
• Сортировка карт в руке - классическая аналогия, буквально описывающая механику алгоритма.