Вид вставки является алгоритмом сортировки с временной сложностью худшего случая O (n ²) и временной сложностью лучшего случая Θ (n). Это создает заключительный массив движущимися элементами вверх в отсортированное положение по одному.
В отличие от многих алгоритмов сортировки с квадратичной временной сложностью, это на самом деле применяется на практике для сортировки небольших массивов данных.
Массив фактически разделен на две части - отсортированный префикс и неотсортированный суффикс. Вначале, отсортированная часть содержит первый элемент массива, и неотсортированный содержит все остальные. На каждом шаге алгоритм берет первый элемент в неотсортированной части и вставляет его в правильное место в отсортированной части. Когда неотсортированная часть становится пустой, остановки алгоритма.
Этот алгоритм очень эффективен для данных, которые уже являются в порядке или почти в порядке. Время выполнения является O (n), если расстояние, которое должен переместить любой элемент, ограничено константой.