|[+] Integer: sorting in linear time for w = Ω(lg2+ε n), priority queues||Scribe Notes [src]|
This lecture is about the state-of-the-art in sorting and priority
queues on a word RAM. An equivalence by Thorup shows that any sorting
algorithm can be transformed into a priority queue with operations taking
1/nth the time to sort. So these are really one and the same problem.
The best results we know for sorting in linear time (and thus for constant-time priority queues) is when w = O(lg n) and when w = Ω(lg2+ε n). The first result is just radix sort. The second result is the main topic of the lecture: a fancy word-RAM algorithm called signature sorting. It uses a combination of hashing, merge sort, and parallel sorting networks.
The range of w in between lg and lg2+ε remains unsolved. The best algorithm so far runs in O(n √lg lg n) expected time.
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.