о сортировках

[wizzard]

уважаемые товарищи!

а почему все считают, что сортировка произвольных данных inplace может выполняться за N log(N), если с 1985 1978 года у нас есть модификация бинарного поиска, работающая за log(log(N))?

ведь тогда, даже если взять банальную сортировку вставкой, асимптотика должна быть N*log(log(N)), или я чего-то недопонимаю?

UPD: блин, сортировка вставкой ведь еще двигать элементы должна, а в связном списке interpolation search невозможен.. надо сделать вариант Library sort и померять.

UPD2: а вот и N log log N сортировка от Yijie Han – yijie.han-loglogn-sort.pdf, спасибо 184467440737095 за наводку. Надо бы реализовать и потестить))

Comments

[slobin.livejournal.com]

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

... Intrat et exit ut nil supra ...

[bik-top.livejournal.com]

Проверил: у Кнута и у Кормена-Лейзерсона-Ривеста «нормальный» рассчёт асимптотики, а не «академический».

[slobin.livejournal.com]

В данном случае не важно: я утверждаю, что даже сравнений (игнорируя пересылки) потребуется не менее n*log(n) в худшем случае. Учёт пересылок может только ухудшить оценку. Это называется "энтропийная оценка": чтобы отсортировать массив, нам нужно добыть откуда-то не менее n*log(n) бит информации. Если единственным источником информации является сравнение на больше-меньше, то вот столько их и будет. Если разрешены другие источники информации (например, выделение отдельных битов из данных), то будет вот столько обращений к этим другим источникам.

... Какой я математик? Я флюктуация. ...