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

Вставляем элемент в уже готовую часть

Сортировка вставками считает первый элемент отсортированным префиксом, а затем берёт следующий элемент и вставляет его в подходящее место слева. Чтобы освободить позицию, большие элементы префикса сдвигаются на одну ячейку вправо.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int value = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > value) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = value;
    }
}

Значение value временно сохраняется отдельно. Пока слева встречаются элементы больше него, они сдвигаются вправо. Когда цикл заканчивается, позиция j + 1 и есть место вставки. После каждой итерации диапазон от 0 до i полностью отсортирован.

Почему почти отсортированные данные удобны

Если элементы уже находятся близко к своим правильным позициям, внутренний цикл делает мало сдвигов. Для полностью отсортированного массива условие a[j] > value сразу ложно на каждом шаге, поэтому время становится O(n).

В среднем и в худшем случае сортировка вставками имеет сложность O(n²), а дополнительная память равна O(1). Для небольших или почти отсортированных массивов она может быть вполне практичной именно из-за малого служебного расхода.