Sorting algorithms

Five classic sorts, from the simplest to the most efficient. For each one: the idea, a short example and the pitfall to avoid.

Overview

Sort	Best case	Worst case	Memory	Stable
Insertion	O(n)	O(n²)	O(1)	yes
Selection	O(n²)	O(n²)	O(1)	no
Merge	O(n log n)	O(n log n)	O(n)	yes
Quick	O(n log n)	O(n²)	O(log n)	no
Heap	O(n log n)	O(n log n)	O(1)	no

A sort is stable if it keeps the relative order of equal elements. This matters when sorting records on several keys: sorting by first name, then stably by last name, gives a list ordered by last name, then first name.

Insertion sort

The left part of the array is always sorted. At each round, take the first element of the unsorted part (the key), shift the sorted elements larger than it one slot to the right, and drop the key into the gap.

Watch insertion sort

Height shows value. Each letter follows the same element as it moves.

Start: 5, 2, 8, 1, 6, 3, 7, 4.

Without animation, here is the final result: [1, 2, 3, 4, 5, 6, 7, 8]. The lesson explanations remain available below.

Example: [5, 2, 8, 1]

key 2: 5 shifts → [2, 5, 8, 1]
key 8: 8 ≥ 5, nothing to shift
key 1: 8, 5 and 2 shift → [1, 2, 5, 8]

On a nearly sorted array there are very few shifts: that is why its best case is O(n). Shifting stops at the first element ≤ the key, which keeps the sort stable.

Selection sort

For each position i, find the minimum of the unsorted part A[i..n−1] and swap it with A[i].

Watch selection sort

Height shows value. Each letter follows the same element as it moves.

Start: 5, 2, 8, 1, 6, 3, 7, 4.

Without animation, here is the final result: [1, 2, 3, 4, 5, 6, 7, 8]. The lesson explanations remain available below.

Example: [5, 2, 8, 1] → the minimum 1 goes to index 0: [1, 2, 8, 5] → 2 is already in place → the minimum 5 goes to index 2: [1, 2, 5, 8].

It always makes O(n²) comparisons, even on a sorted array, but at most n − 1 swaps. A long-distance swap can move an element past another one with the same value: the sort is not stable.

Merge sort

Split the array into two halves, sort each half recursively, then merge the two sorted lists: compare their heads and take the smaller one, until one list runs out, then copy the rest of the other.

Watch merge sort

Height shows value. Each letter follows the same element as it moves.

Start: 5, 2, 8, 1, 6, 3, 7, 4.

Without animation, here is the final result: [1, 2, 3, 4, 5, 6, 7, 8]. The lesson explanations remain available below.

Merge example: L = [2, 5, 8], R = [1, 3, 9]

2 vs 1 → 1; 2 vs 3 → 2; 5 vs 3 → 3; 5 vs 9 → 5; 8 vs 9 → 8
L is empty: copy 9 → [1, 2, 3, 5, 8, 9]

The recurrence T(n) = 2T(n/2) + O(n) gives O(n log n) in every case (case 2 of the master theorem). On a tie, take from the left: that is what makes the sort stable. Its drawback is the auxiliary array of size n.

Quicksort (Lomuto partition)

Choose a pivot (here, the last element), put everything ≤ pivot on its left and everything larger on its right, then sort both sides recursively.

Watch quick sort

Height shows value. Each letter follows the same element as it moves.

Start: 5, 2, 8, 1, 6, 3, 7, 4.

Without animation, here is the final result: [1, 2, 3, 4, 5, 6, 7, 8]. The lesson explanations remain available below.

partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1
    for j from lo to hi - 1:
        if A[j] <= pivot:
            i = i + 1
            swap A[i] and A[j]
    swap A[i + 1] and A[hi]
    return i + 1

Example: [5, 2, 8, 1, 9, 3], pivot 3.

j = 0: 5 > 3, nothing
j = 1: 2 ≤ 3 → i = 0, swap A[0] and A[1] → [2, 5, 8, 1, 9, 3]
j = 2: 8 > 3, nothing
j = 3: 1 ≤ 3 → i = 1, swap A[1] and A[3] → [2, 1, 8, 5, 9, 3]
j = 4: 9 > 3, nothing
end: swap A[2] and the pivot → [2, 1, 3, 5, 9, 8]. The pivot 3 is in its final position.

The worst case. With the last element as pivot, an already sorted array gives partitions of size n − 1 and 0 every time: O(n²). In practice, a random pivot or the median of three is often used to avoid it.

Other partition schemes exist (Hoare, for example); they produce different steps. Check which one your course uses.

Heapsort

Watch heap sort

Height shows value. Each letter follows the same element as it moves.

Start: 5, 2, 8, 1, 6, 3, 7, 4.

Without animation, here is the final result: [1, 2, 3, 4, 5, 6, 7, 8]. The lesson explanations remain available below.

Turn the array into a max-heap in O(n) (see heaps).
The root is the maximum: swap it with the last element of the heap. It is now in its final position.
The heap shrinks by one slot and the new root sifts down. Repeat until the heap is empty.

O(n log n) in every case and no extra memory. Long-distance swaps make it unstable.

Which one to choose?

Small or nearly sorted array: insertion.
Need stability and a guaranteed worst case: merge. TimSort, used by Python and by Java for objects, combines merge and insertion.
Fastest on average: quick, with a good pivot choice.
Guaranteed O(n log n) with no extra memory: heap.