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

 Допустим, что записи t₀…t_k-1 уже упорядочены. В упорядоченной части последовательности найдем место для t_k, на котором ключ записи t_k не нарушает порядка, и вставим запись туда, предварительно сдвинув вправо на одну позицию записи от места вставки до t_k. Также поступим с последующими записями.
 При поиске места вставки k-й записи необходимо пройти в среднем k/2 ключей, выполняя сравнения и сдвиги. Таким образом, порядок времени работы алгоритма опять составляет величину порядка N², где N – число записей.
 Время поиска места вставки можно уменьшить до ~log₂N, используя дихотомию, однако количество сдвигов от этого не уменьшится.