main page  —  COMP 526 Applied Algorithmics

Unit 3: Efficient Sorting – The Power of Divide & Conquer

This unit covers

  • mergesort and quicksort
  • counting sort
  • comparions lower bound for sorting
  • adaptive sorting
  • further divide & conquer algorithms

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.

Material

Part I – The Basics

Part II – Exploiting presortedness

  • Video 3-5 (2023-10-19): §3.5 Adaptive sorting & Peeksort

  • Video 3-6 (2023-10-19): §3.6 Python’s list sort & Powersort

Part III – Divide & conquer beyond sorting

  • Video 3-7 (2023-10-20): §3.7 Order statistics, quickselect, median of medians

  • Video 3-8 (2023-10-20): §3.8 Further divide & conquer algorithms


Further reading and sources

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

The exposition of adaptive sorting is my own and based on several sources:

The presentation of quickselect and the median-of-medians algorithm is inspired by material prepared for the module

The other material of Part III is based on


Unit 2  ⋅  Syllabus  ⋅  Unit 4