Unit 3: Efficient Sorting

This is an archived version of this module from Spring 2020.
Click here for the current iteration.

This unit covers

• mergesort and quicksort
• counting sort
• parallel RAM model
• parallel prefix sums
• parallel mergesort and quicksort

Learning outcomes

1. Know principles and implementation of mergesort.
2. Know principles and implementation of quicksort.
3. Know properties and performance characteristics of mergesort and quicksort.
4. Know the comparison model and understand the corresponding lower bound.
5. Understand counting sort and how it circumvents the comparison lower bound.
6. Understand and use the parallel random-access-machine model in its different variants.
7. Be able to analyze and compare simple shared-memory parallel algorithms by determining parallel time and work.
8. Understand efficient parallel prefix sum algorithms.
9. Be able to devise high-level description of parallel quicksort and mergesort methods.

Material

Lecture notes and video will be added once available.

• lecture notes
• tutorial problems
• slides
• Lecture 2020-02-18 on Mergesort & Quicksort

• Lecture 2020-02-18 on Comparison Lower Bound

• Lecture 2020-02-24 on Integer Sorting

• Lecture 2020-02-24 on Parallel Models of Computation

• Lecture 2020-02-24 on Parallel Primitives

• Lecture 2020-02-25 on Parallel Primitives (cont)

• Lecture 2020-02-25 on Parallel Sorting

Further reading and sources

More elementary sorting methods are described in detail in Algorithms 4th ed.

• Sedgewick, Wayne: Algorithms 4th ed (2011), Pearson
• Algorithms 4th ed booksite

The presentation of parallel methods takes some inspiration from Uzi Vishkin’s class notes:

• Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques