Start learning →

Sorting

The simple O(n²) sorts, then merge sort, quick sort and heap sort, and counting sort, which avoids comparing items altogether. You compare them on time, memory and stability.

About 11 hours of study

Learning objectives

Lessons

  1. 1

    Bubble, selection and insertion sort

    Three O(n²) sorts, step by step: swapping neighbours, picking the minimum, and inserting into a sorted part.

  2. 2

    Merge sort

    Divide and conquer: split the array in half, sort each half recursively, and merge two sorted halves in O(n).

  3. 3

    Quick sort

    Partition around a pivot, sort each side recursively; O(n log n) on average, O(n²) when the pivots are bad.

  4. 4

    Heap sort and counting sort

    Heap sort: O(n log n) in place. Counting sort: O(n + k) without comparing, and why comparison sorts cannot beat n log n.

Module practice

Module quiz

1. Which of these sorts is stable as taught in this course?
2. How many comparisons does selection sort make on an array that is already sorted?
3. Insertion sort runs on {5, 2, 4, 1}. What does the array look like after the first two insertions?
4. A Lomuto partition with the last item as pivot runs on {3, 7, 1, 4}. At which index does the pivot end up?
5. How many levels of merging does merge sort do on 16 items?
6. Which data is a poor fit for counting sort?
7. Quick sort with the last item as pivot runs on n items already in increasing order. How deep does the recursion go?

‹ Analysis and searchingBacktracking, greedy and dynamic programming ›