6.851: Advanced Data Structures (Fall'17)

Prof. Erik Demaine TAs: Adam Hesterberg, Jayson Lynch

[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 14 Video [previous] [next] [completion form]

[+] Integer: sorting in linear time for w = Ω(lg^2+ε n), priority queues

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 = Ω(lg^2+ε 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 lg^2+ε remains unsolved. The best algorithm so far runs in O(n √lg lg n) expected time.

Download Video: 360p, 720p

Lecture notes, page 1/7 • [previous page] • [next page] • [PDF]

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.