main page  —  COMP 526 Applied Algorithmics

# Unit 3: Efficient Sorting

This is an archived version of this module from Spring 2022.

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 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

### Part I – The Basics

• Video 3-1 (2022-02-17): §3.0 Sorting introduction

• Video 3-2 (2022-02-17): §3.1 Mergesort

• Video 3-3 (2022-02-17): §3.2 Quicksort

• Video 3-4 (2022-02-17): §3.3 Comparison-based lower bound

• Video 3-5 (2022-02-17): §3.4 Integer sorting

### Part II – Exploiting presortedness

• Video 3-6 (2022-02-21): §3.5 Adaptive sorting

• Video 3-7 (2022-02-21): §3.6 Python’s list sort & Powersort

### Part III – Sorting with many processors

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

• Video 3-9 (2022-02-24): §3.8 Parallel primitives, prefix sum

• Video 3-10 (2022-02-24): §3.9 Parallel sorting