Sorting in time O(n log log n)
Speaker: Stefan Nilsson, Nada, KTH
Tid: On 1999-11-10 kl 15.00 - On 2013-10-23 kl 11.00
Plats: room 1537
Abstract:
A fast algorithm for the "standard sorting problem" is presented. It sorts n word-sized integers on a unit-cost RAM in O(n log log n) worst-case time. The algorithm appeared in a rather inaccessible paper ("Sorting in linear time?" by A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, STOC'95) but is actually quite simple.