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

[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]

Всё, сплю на ходу. В рамках этой дискуссии я насчитал уже, кажется, три (или больше?) существенно разных постановки задачи. И я сам их периодически путаю, пытаясь применить к одной результаты от другой. Получается чушь. :-( Прошу прощения, пошёл спать.

... Поймите меня хотя бы неправильно ...