Введение

Алгоритмы сортировки, использующие существующий порядок во входных данных. Алгоритм сортировки относится к семейству адаптивных алгоритмов, если он использует преимущества уже существующего порядка во входных данных. Он выигрывает от предварительно отсортированной входной последовательности – или ограниченного уровня беспорядка, в зависимости от определения меры беспорядка – и сортирует быстрее. Адаптивная сортировка обычно реализуется путем модификации существующих алгоритмов сортировки.

Мотивация

Сравнительные алгоритмы сортировки традиционно стремились к достижению оптимальной границы O(n log n) при анализе временной сложности. Адаптивная сортировка использует существующий порядок входных данных, чтобы добиться более высокой производительности, так что время, необходимое алгоритму для сортировки, является плавной функцией размера последовательности и степени её неупорядоченности. Иными словами, чем ближе входные данные к отсортированному состоянию, тем быстрее они должны быть отсортированы. Это привлекательное свойство для алгоритма сортировки, поскольку на практике часто встречаются почти отсортированные последовательности. Таким образом, производительность существующих алгоритмов сортировки можно улучшить, учитывая существующий порядок входных данных. Большинство алгоритмов сортировки, оптимально работающих в наихудшем случае, таких как сортировка кучей и сортировка слиянием, не учитывают существующий порядок во входных данных, хотя этот недостаток легко устраняется в случае сортировки слиянием путем проверки, меньше ли (или равен) последний элемент левой группы первому элементу правой группы, в этом случае операцию слияния можно заменить простой конкатенацией – модификацией, которая вполне соответствует принципам адаптивности алгоритма.

Примеры

Классическим примером адаптивного алгоритма сортировки является сортировка вставками. Шелсортировка, smoothsort, сплейсортировка, Timsort и сортировка по картезианскому дереву.