В чем разница между этими двумя алгоритмами сортировки nloglog (n)? (Андерссон и др., 1995 против Хан, 2004)

Question

Комментарий Свейнпола здесь приводит меня к этой статье . Затем, ища реализацию в C, я наткнулся на this , который ссылается на другую статью об алгоритме, описанном здесь .

Обе статьи описывают алгоритмы целочисленной сортировки, которые выполняются за время O (nloglog (n)). Какая разница между двумя? Были ли какие-либо более свежие выводы по этой теме?

Андерссон и др., 1995

Хан, 2004

Answer 1

Из аннотации к Ханьской бумаге:

Это также улучшает предыдущий лучший детерминированный алгоритм сортировки [A. Андерссон, Т. Хагеруп, С. Нильссон, Р. Раман, в кн .: Учеб. Симпозиум 1995 года по Теория вычислений (1995) 427–436; Y. Хан, X. Шен, в: Proc. 1995 Международные вычисления и Комбинаторная конференция, в: Лекция Заметки в комп. Sci. 959 (1995) 324–333] который сортирует по O (nloglogn) время, но использует O (M ^ E) пространство. Наши результаты также улучшает результат Андерссона и другие. [A. Андерссон, Т. Хагеруп, С. Нильссон, Р. Раман, в: Proc. 1995 Симпозиум по теории вычислений (1995) 427–436] который сортирует в O (nloglogn) время и линейное пространство, но использует рандомизацию.

Итак, есть две работы Андерсона и др. Один использует пространство O (m ^ e), а другой использует рандомизацию, но линейное пространство. Бумага Хана детерминирована с линейным пространством.