Sorting in time O(n log log n)
Speaker: Stefan Nilsson, Nada, KTH
Time: Wed 1999-11-10 15.00 - Wed 2013-10-23 11.00
Location: 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.