сортировка вставкой

EN: insertion sort

Алгоритм сортировки сравнением, строящий отсортированный результат по одному элементу: каждый новый элемент сдвигается влево на правильную позицию среди уже отсортированных. Время — O(n²) в среднем и худшем случае; O(n) в лучшем — на почти отсортированных данных. Устойчив, работает на месте, предпочтителен для очень малых массивов.