2.6.1 Введение

В предыдущих разделах были рассмотрены различные алгоритмы, которые могут отсортировать п чисел за время О(пlog n). Алгоритмы сортировки слиянием (merge sort) и сортировки с помощью кучи (heap sort) работают за такое время в худшем случае, а у алгоритма быстрой сортировки таковым является среднее время работы. Оценка O(nlog n) точна: для каждого из этих алгоритмов можно предъявить последовательность из п чисел, время обработки которой будет (nlog n).

Все упомянутые алгоритмы проводят сортировку, основываясь исключительно на попарных сравнениях элементов, поэтому их иногда называют сорти­ровками сравнением (comparison sort). В дальнейшем будет доказано, что алгоритм такого типа сортирует п элементов за время не меньше (nlog n) в худшем случае. Тем самым алгоритмы сортировки слиянием и с помощью кучи асимптотически оптимальны: не существует алгоритма сортировки сравнением, который превосходил бы указанные алгоритмы более чем в конечное число раз.

Три алгоритма сортировки – сортировка подсчётом, цифровая сортировка и сортировка вычерпыванием могут работать за линейное время. Разумеется, они улучшают оценку (nlog n) за счёт того, что используют не только попарные сравнения, но и внутреннюю структуру сортируемых объектов, т.е. дополнительную априорную информацию. Без использования дополнительной информации сортировка за линейное время невозможна.

Говорят, что алгоритм сортировки основан на сравнениях, если он никак не использует внутреннюю структуру сортируемых элементов, а лишь сравнивает их и после некоторого числа сравнений выдаёт ответ (указывающий истин­ный порядок элементов).