Sleep sort

[jayrandom]

И я считаю, что Sleep sort - гениальный алгоритм для сортировки.

Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду.

Самое важное в этом примере - принцип замены измерения пространства измерением времени.
Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом.

Comments

[jayrandom.livejournal.com]

Правильно, это и есть в некотором роде "гистограмма". Но для хранения гистограммы нужно место (плюс структуры для манипуляции), а тут гистограмма (или процесс её построения) погружён во время.

[a_p]

для хранения тредов места тоже нужно немало. Вообще, подобный алгоритм нужно в специализированном железе имплементировать.