Сортировка вставкой - EcsFlash/DataTypes GitHub Wiki

Cуть

Идея: Массив условно делится на отсортированную (слева) и неотсортированную (справа) части.

Шаги:

Берётся очередной элемент из неотсортированной части (v = arr[i]).

Он последовательно сравнивается с элементами отсортированной части (справа налево).

Если arr[j] > v, то элементы сдвигаются вправо, чтобы освободить место для v.

Когда находится правильная позиция (arr[j] <= v), элемент v вставляется на своё место.

Итог: После прохода по всем элементам массив становится отсортированным.

Красивая анимация

Псевдокод

func InsertionSort(arr []int) []int {
	for i := 1; i < len(arr); i++ {
		j := i - 1
		for j >= 0 && arr[j] > arr[j+1] {
			swap(&arr[j], &arr[j+1])
			j--
		}
	}
	return arr
}

┌────────────┬────────────────┬──────────────────┬────────────────┐
│            │  Лучший случай │  Средний случай  │  Худший случай │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Время**  │     O(n)       │      O(n²)       │     O(n²)      │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Память** │     O(1)       │      O(1)        │     O(1)       │
└────────────┴────────────────┴──────────────────┴────────────────┘