Сортировочный номер

В математике и информатике числа сортировки представляют собой последовательность чисел, введенную в 1950 году Хьюго Штейнхаусом для анализа алгоритмов сортировки сравнением . Эти числа дают наихудшее количество сравнений, используемых как при двоичной сортировке вставкой, так и при сортировке слиянием . Однако существуют другие алгоритмы, которые используют меньше сравнений.

Формула и примеры

The $n$номер сортировки определяется по формуле

$n\,S(n)-2^{S(n)}+1,$

где

$S(n)=\lfloor 1+\log _{2}n\rfloor .$

Последовательность чисел, заданная этой формулой (начиная с $n=1$) является

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... (последовательность A001855 в OEIS ).

Эту же последовательность чисел можно получить и из рекуррентного соотношения ,

$A(n)=A{\bigl (}\lfloor n/2\rfloor {\bigr )}+A{\bigl (}\lceil n/2\rceil {\bigr )}+n-1$

или закрытая форма

$A(n)=n\lceil \log _{2}n\rceil -2^{\lceil \log _{2}n\rceil }+1.$

Это пример 2-регулярной последовательности .

Асимптотически значение $n$число сортировки колеблется примерно между $n\log _{2}n-n$ и $n\log _{2}n-0.915n,$ в зависимости от соотношения между $n$ и ближайшая степень двойки .

Приложение к сортировке

В 1950 году Хьюго Штейнхаус заметил, что эти числа подсчитывают количество сравнений, используемых при двоичной сортировке вставками , и предположил (ошибочно), что они дают минимальное количество сравнений, необходимое для сортировки. $n$ элементы, использующие любую сортировку сравнения . Гипотеза была опровергнута в 1959 году Л. Р. Фордом-младшим и Селмером М. Джонсоном , которые нашли другой алгоритм сортировки, сортировку слиянием-вставкой Форда-Джонсона , использующий меньшее количество сравнений.

Та же самая последовательность чисел сортировки также дает наихудшее количество сравнений, используемых при сортировке слиянием для сортировки. $n$ предметы.

Другие приложения

Числа сортировки (сдвинутые на одну позицию) также дают размеры кратчайших возможных супершаблонов для слоистых перестановок .