Оптимальная сортировка

Сортировка с минимальным числом сравнений

Задача «найти алгоритм сортировки с минимальным числом сравнений» может показаться некорректной, потому что вообще минимальное число сравнений 00, ведь есть алгоритмы, не требующие сравнений.

Но мы сейчас говорим только об алгоритмах сортировки, которые сортируют элементы множества с заданным на нём отношением линейного порядка. В этом контексте понятно, что сравнение — единственная доступная нам операция, поэтому придумывать алгоритмы с наименьшим числом сравнений вполне содержательная и интересная задача.

Оценка снизу

Пусть kk — минимальное число сравнений, достаточное для сортировки nn элементов. На вопрос «находятся ли два элемента в отношении ⩽\le?» можно ответить только двумя способами: да и нет. Здесь ⩽\le — отношение, по которому производится сортировка.

По ответам на kk вопросов нам нужно однозначно понять, какая из n!n! перестановок исходных элементов является их отсортированным порядком. Значит,

n!⩽2kn! \le 2^k

Применяя формулу Стирлинга для неравенства k⩾⌈log⁡2n!⌉k \ge \lceil \log_2 n! \rceil, получаем оценку

k⩾nlog⁡2n−n/ln⁡2+log⁡2n/2+O(1)k \ge n \log_2 n - n / \ln 2 + \log_2 n / 2 + O(1)

Этой оценки почти достигают некоторые разобранные ранее алгоритмы.

Подходит алгоритм бинарных вставок, количество сравнений в котором выражается формулой

∑k=1n⌈log⁡2n⌉=n⋅⌈log⁡2n⌉−2⌈log⁡2n⌉+1=nlog⁡2n−n+O(1)\sum\limits_{k=1}^n \lceil \log_2 n \rceil = n \cdot \lceil \log_2 n \rceil - 2^{\lceil \log_2 n \rceil} + 1 = n \log_2 n - n + O(1)