Insertion Sort

Массив мысленно делится на отсортированный префикс (изначально — один первый элемент) и неотсортированный остаток. На каждом шаге берётся первый элемент остатка и сдвигается влево, пока не встанет на своё место относительно префикса — после чего префикс увеличивается на один элемент. Инвариант "префикс уже отсортирован" держится на каждом шаге, поэтому корректность алгоритма очевидна прямо из построения.The array is conceptually split into a sorted prefix (initially just the first element) and an unsorted remainder. At each step, the remainder's first element is taken and shifted left until it lands in its correct place relative to the prefix — after which the prefix grows by one element. The invariant "the prefix is already sorted" holds at every step, so the algorithm's correctness follows directly from its construction.

void insertion_sort(std::vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) {
        int key = a[i];
        int j = int(i) - 1;
        while (j >= 0 && a[j] > key) { // сдвигать, пока не найдётся место// shift until the right spot is found
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

Столбики — случайный массив, размер которого можно задать ниже. Зелёная заливка — отсортированный префикс, жёлтая — текущий "key" (взятый элемент), который двигается влево, пока не найдёт своё место.The bars are a random array whose size can be set below. Green fill is the sorted prefix, yellow is the current "key" element being shifted left until it finds its spot.

В худшем случае (массив отсортирован по убыванию) каждый элемент сдвигается через весь префикс — Θ(n²) сравнений и сдвигов. Но на уже отсортированном или почти отсортированном входе внутренний while почти никогда не выполняется — Θ(n). Это и есть адаптивность: время работы зависит не только от n, но и от того, насколько вход уже упорядочен, а точнее — от числа "инверсий" (пар элементов не в том порядке). Ни quicksort, ни heapsort, ни selection sort в чистом виде этим свойством не обладают.In the worst case (a descending array) every element shifts through the entire prefix — Θ(n²) comparisons and shifts. But on an already-sorted or nearly-sorted input, the inner while loop almost never executes — Θ(n). This is adaptivity: the running time depends not just on n but on how ordered the input already is, more precisely on the number of "inversions" (pairs of elements out of order). Neither quicksort, heapsort, nor selection sort in their pure form have this property.

Именно адаптивность и малые константы делают insertion sort стандартным выбором для маленьких подмассивов (обычно <16 элементов) внутри гибридных алгоритмов вроде IntroSort и Timsort — на таком масштабе O(n²) практически неотличимо от O(n log n), а накладные расходы рекурсии quicksort/merge sort — нет.Adaptivity and small constants are exactly why insertion sort is the standard choice for small subarrays (usually <16 elements) inside hybrid algorithms like IntroSort and Timsort — at that scale O(n²) is practically indistinguishable from O(n log n), while the recursion overhead of quicksort/merge sort isn't.