Unit 3: Efficient Sorting

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

This unit covers

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

Learning outcomes

1. Know principles and implementation of mergesort and quicksort.
2. Know properties and performance characteristics of mergesort and quicksort.
3. Know the comparison model and understand the corresponding lower bound.
4. Understand counting sort and how it circumvents the comparison lower bound.
5. Know ways how to exploit presorted inputs.
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

• slides
• lecture notes

Part I – The Basics

• Video 3-1 (2022-02-17, 13:18): §3.0 Sorting introduction
  
  Chapters

  0:18 Learning Outcomes
  1:22 Overview
  1:38 Motivation
  4:17 Sorting
  7:11 Complexity
  
• Video 3-2 (2022-02-17, 17:47): §3.1 Mergesort
  
  Chapters

  0:12 Clicker Question
  3:04 Merging sorted lists
  14:37 Mergesort - Discussion
  
• Video 3-3 (2022-02-17, 19:18): §3.2 Quicksort
  
  Chapters

  1:25 Clicker Question
  1:47 Partitioning around a pivot
  6:27 Partitioning - Detailed code
  10:21 Quicksort & Binary Search Trees
  14:44 Quicksort - Worst Case
  16:24 Randomized Quicksort - Analysis
  17:44 Quicksort - Discussion
  
• Video 3-4 (2022-02-17, 15:11): §3.3 Comparison-based lower bound
  
  Chapters

  3:20 The Comparison Model
  7:35 Comparison Lower Bound
  13:33 Clicker Question
  
• Video 3-5 (2022-02-17, 10:18): §3.4 Integer sorting
  
  Chapters

  2:05 Counting Sort
  6:32 Radix Sort
  

Part II – Exploiting presortedness

• Video 3-6 (2022-02-21, 39:20): §3.5 Adaptive sorting
  
  Chapters

  0:23 Adaptive sorting
  6:06 Warmup: check for sorted inputs
  12:41 Mergesort with sorted check - Analysis
  17:44 Alignment issues
  25:35 Natural Bottom-Up Mergesort - Analysis [2]
  26:52 Good merge orders
  31:16 Nearly-Optimal Mergesort
  
• Video 3-7 (2022-02-21, 21:21): §3.6 Python’s list sort & Powersort
  
  Chapters

  0:17 Sorting in Python
  4:34 Timsort (original version)
  16:16 Powersort-Computing powers
  19:49 Powersort - Discussion
  

Part III – Sorting with many processors

• Video 3-8 (2022-02-24, 34:47): §3.7 Parallel computation, PRAM
  
  Chapters

  2:55 Parallel computation
  10:25 PRAM models
  19:47 Time
  22:16 Work efficiency
  25:20 Why work
  25:45 Brents theorem
  26:42 Parallel time
  
• Video 3-9 (2022-02-24, 33:32): §3.8 Parallel primitives, prefix sum
  
  Chapters

  1:37 Clicker Question
  3:16 Prefix sums - Sequential
  7:21 Parallel prefix sums New Compute all prefix sumns with balanced trees in parallel Remember partial results for reuse
  11:06 Parallel prefix sums - Code
  17:23 Work-efficient parallel prefix sums standard trick to improve work compute small blocks sequentially
  27:52 Compacting subsequences
  
• Video 3-10 (2022-02-24, 14:14): §3.9 Parallel sorting
  
  Chapters

  0:29 Parallel quicksort Let's try to parallelize quicksort
  3:34 Parallel quicksort - Code
  5:57 Parallel quicksort - Analysis Time
  10:21 Parallel mergesort - Analysis
  12:11 Parallel sorting - State of the art
  

---

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 exposition of adaptive sorting is my own and based on several sources:

• Tim Peters’s description of CPython’s list.sort algorithm
• Munro, Wild: Nearly Optimal Mergesorts, ESA 2018
• Gaurav Sen: Tim sort explained, Part 1, Part 2, Part 3, Part 4.
  Sequence of videos explaining Timsort’s other tricks (prior to adopting powersort’s merge rules).

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

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

---

Unit 2  ⋅  Syllabus  ⋅  Unit 4