Комментарий Swanepoel here привести меня к this paper. Затем, ища реализацию в C, я наткнулся на this, который ссылался на another paper на алгоритм, описанный here.В чем разница между этими двумя алгоритмами сортировки nloglog (n)? (Andersson et al., 1995 vs. Han, 2004)
В обеих документах описываются целые алгоритмы сортировки, которые выполняются в O (nloglog (n)) времени. Какая разница между двумя? Были ли более поздние выводы по этой теме?
Из реферата Хань бумаги:
Это также улучшает предыдущий лучший алгоритм детерминированных сортировок [A. Андерссон, Т. Хагеруп, С. Нильссон, Р. Раман, в: Proc. 1995 год Симпозиум по Теория вычислений (1995) 427-436; Y. Хань, Х. Шен, в: Proc. 1995 Международная вычислительная техника и Комбинаторная конференция, в: Лекция Примечания в Comput. Sci. 959 (1995) 324-333], который сортирует по O (nloglogn) времени, но использует O (m^e) пространство. Наши результаты также улучшают результаты Andersson et al. [A. Андерссон, Т. Хагеруп, С. Нильссон, Р. Раман, в: Proc. 1995 Симпозиум по теории вычислений (1995) 427-436], который сортирует по O (nloglogn) время и линейное пространство, но использует рандомизацию.
Итак, есть две книги Андерсона и др. Один использует O (m^e) пространство и другие использует рандомизацию, но линейное пространство. Ханская бумага детерминирована линейным пространством.