Lesson 1 · Core algorithms

Sorting Algorithms: Methods and Performance

Sorting algorithms differ less in what they produce than in how they get there and what they cost. The comparison-based methods are bounded below by O(n log n); the practical choice among them turns on memory use, stability, and how they behave on the data you actually have.

The Four Axes That Matter

Every sorting algorithm sorts, so the choice between them turns on four properties. Naming them is what makes a comparison an analysis rather than a list.

Time complexity, and specifically which case. Quicksort is O(n log n) average and O(n²) worst; merge sort is O(n log n) always. Whether the worst case matters depends on whether an adversary controls the input.

Space. An in-place sort uses O(1) auxiliary memory beyond the array — heap sort and in-place quicksort qualify, though quicksort's recursion adds O(log n) of stack. Merge sort needs an O(n) buffer, which for a large array may be the deciding factor.

Stability. A sort is stable if elements comparing equal keep their original relative order. This matters more than it first appears: sorting records by one key and then by another only produces a correct multi-key ordering if the second sort is stable. Merge and insertion sort are stable; quicksort and heap sort are not.

Adaptivity. An adaptive sort runs faster on input that is already nearly sorted. Insertion sort is O(n) on sorted input and O(n²) on reversed input — a difference of a factor of n from the data alone. Since real data is frequently partially ordered, this is a genuine advantage rather than a curiosity.

A fifth consideration appears at scale: whether the algorithm accesses memory sequentially. Quicksort's partitioning scans linearly and is cache-friendly; heap sort jumps between parent and child indices far apart in the array. This is why quicksort usually beats heap sort in practice despite the worse worst case.

Time — and which case, since worst and average often differ
Space — in-place O(1) against merge sort's O(n) buffer
Stability — required for correct multi-key sorting
Adaptivity and cache behaviour decide real-world speed

Why O(n log n) Is a Wall

No comparison-based sorting algorithm can beat O(n log n) in the worst case. This is not a statement about current algorithms — it is a proof about the problem, and being able to give it is a standard exam requirement.

The argument is information-theoretic. An algorithm that learns only through pairwise comparisons is navigating a decision tree: each comparison has two outcomes, so each internal node has two children, and each leaf is one possible ordering of the input.

There are n! possible orderings, so the tree must have at least n! leaves. A binary tree with n! leaves has height at least log₂(n!), and by Stirling's approximation log₂(n!) is Θ(n log n).

The height of the tree is the number of comparisons in the worst case — the longest root-to-leaf path. So Ω(n log n) comparisons are necessary, and since merge sort and heap sort achieve it, the bound is tight.

Two consequences follow. Merge sort and heap sort are asymptotically optimal among comparison sorts, and no cleverness will improve them. And any algorithm claiming to sort faster must not be comparing elements — which is exactly what the non-comparison sorts do.

Note what the bound does not say. It says nothing about the average case being better, about partially sorted input, or about constant factors. Timsort is O(n) on already-sorted data because it detects existing runs, which does not contradict the bound — the bound is on the worst case over all inputs.

Comparisons form a decision tree; each leaf is one possible ordering
n! orderings force a height of at least log₂(n!) = Θ(n log n)
Merge and heap sort achieve the bound, so it is tight
Beating it requires not comparing — or an input that is already ordered

The Algorithms Worth Knowing

Bubble sort repeatedly swaps adjacent out-of-order elements. It is O(n²), stable, and has no practical use whatever — it is slower than insertion sort with the same complexity. It is taught because it is easy to explain, and knowing that it is never the right answer is the useful takeaway.

Selection sort finds the minimum and swaps it into place, repeatedly. O(n²) always, not adaptive, not stable in its usual form. Its one distinguishing property is performing exactly n−1 swaps, the minimum possible, which matters only when writes are far more expensive than reads — as on some flash memory.

Insertion sort builds a sorted prefix, inserting each element into position. O(n²) worst case but O(n) on nearly-sorted input, stable, in-place, and with very small constants. This makes it genuinely useful: real libraries switch to insertion sort for subarrays below about 16 elements, where its low overhead beats the recursion of the asymptotically better algorithms.

Merge sort splits the array in half, sorts both recursively, and merges. O(n log n) guaranteed, stable, and predictable — but needs an O(n) buffer. It is the algorithm for linked lists, where it can run in O(1) extra space since merging relinks rather than copies, and for external sorting of data too large for memory, since it reads sequentially.

Quicksort picks a pivot, partitions elements around it, and recurses on both sides. O(n log n) average, in-place, and the fastest in practice because partitioning is a cache-friendly linear scan. Its worst case is O(n²), triggered when the pivot is consistently extreme — which a naive first-element pivot produces on already-sorted input, the most common real case. The remedies are median-of-three or a random pivot; randomisation also defends against deliberately crafted adversarial input.

Heap sort builds a heap in O(n) and extracts the maximum n times. O(n log n) guaranteed and O(1) space — the only common algorithm with both. It is nonetheless slower than quicksort in practice because sift-down jumps between distant indices, defeating the cache. Its niche is as a guaranteed fallback.

Shell sort runs insertion sort over shrinking gaps, so a value far from its home moves many positions in a single step instead of shifting one at a time. Its complexity depends on the gap sequence — roughly O(n^1.3) for common choices — which makes it hard to analyse but genuinely fast on mid-sized arrays with almost no code and no extra memory.

The four above all compare pairs of elements, and no comparison sort can beat O(n log n). Reading the values themselves instead of comparing them escapes that bound entirely, which is what the next three do.

Counting sort tallies how many times each value occurs, then walks the tally to rebuild the array in order. It runs in O(n + k) for a value range of k, and is stable when built with a prefix-sum pass. It wins decisively when k is small relative to n — sorting exam scores or ages — and becomes useless when the range is wide, since the count array is sized by k, not n.

Radix sort sorts digit by digit, least significant first, using a stable counting sort on each pass. For d digits it costs O(d(n + k)), which beats O(n log n) for fixed-width keys such as 32-bit integers. The stability of each pass is not an optimisation but a correctness requirement: an unstable pass discards the ordering the previous passes established.

Bucket sort spreads values across buckets by range, sorts each bucket, and concatenates. On input uniformly distributed across a known range it averages O(n); when the distribution is skewed and one bucket takes most of the values it degrades to the cost of whatever sorts that bucket. It is the natural fit for floating-point values spread evenly over an interval.

The standard sorts compared
Algorithm	Average	Worst	Space	Stable	Adaptive
Insertion	O(n²)	O(n²)	O(1)	Yes	Yes — O(n) sorted
Selection	O(n²)	O(n²)	O(1)	No	No
Merge	O(n log n)	O(n log n)	O(n)	Yes	No
Quick	O(n log n)	O(n²)	O(log n)	No	No
Heap	O(n log n)	O(n log n)	O(1)	No	No
Counting	O(n + k)	O(n + k)	O(k)	Yes	—
Radix	O(d(n + k))	O(d(n + k))	O(n + k)	Yes	—

Insertion sort is the right choice below ~16 elements
Merge sort: guaranteed and stable, at O(n) space
Quick sort: fastest in practice, O(n²) on a bad pivot choice
Heap sort: guaranteed and in-place, but cache-hostile
Bubble and selection sort are teaching tools, not production code

Key reference

Terms, operations, and practical uses

Sorting properties

StableEqual keys retain their original relative order.
In placeUses only a small amount of auxiliary storage beyond the input.
AdaptiveExisting order reduces the work performed.
Comparison lower boundAny comparison sort needs Ω(n log n) comparisons in the worst case.

Comparison methods

Bubble sortSwaps adjacent pairs until a pass makes none.
Selection sortTakes the smallest remaining value each pass.
Insertion sortPlaces each new item into a sorted prefix.
Merge sortSorts halves, then merges them linearly.
QuicksortPartitions around a pivot, then sorts each side.
HeapsortRemoves the extreme value from a heap, n times.

Non-comparison and hybrid

Counting sortUses the value itself as an index, in O(n + k).
Radix sortOne stable pass per digit, least significant first.
Bucket sortSpreads values across ranges, then sorts each.
Shell sortInsertion sort over shrinking gaps.

Implementation

Sort with insertion sort

def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1
        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1
        values[j + 1] = current
    return values
print(insertion_sort([5, 2, 4, 1]))

#include <iostream>
#include <vector>
using namespace std;
// Insertion sort: grow a sorted prefix by sliding each new value back into place.
void insertionSort(vector<int>& values) {
    for (size_t i = 1; i < values.size(); ++i) {
        int current = values[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0 && values[j] > current) {   // shift larger values right
            values[j + 1] = values[j];
            --j;
        }
        values[j + 1] = current; // drop the key into the gap
    }
}
int main() {
    vector<int> values = {5, 2, 4, 1};
    insertionSort(values);
    cout << "[";
    for (size_t i = 0; i < values.size(); ++i) {
        if (i) cout << ", ";
        cout << values[i];
    }
    cout << "]\n";
}

import java.util.Arrays;
public class Main {
    // Insertion sort: grow a sorted prefix by sliding each new value into place.
    static void insertionSort(int[] values) {
        for (int i = 1; i < values.length; i++) {
            int current = values[i];
            int j = i - 1;
            while (j >= 0 && values[j] > current) {   // shift larger values right
                values[j + 1] = values[j];
                j--;
            }
            values[j + 1] = current; // drop the key into the gap
        }
    }
    public static void main(String[] args) {
        int[] values = {5, 2, 4, 1};
        insertionSort(values);
        System.out.println(Arrays.toString(values));
    }
}

Watch it run

Step through it

Running on [5, 2, 4, 1]

Output

Read all 12 Steps

Choose key 2 The prefix [5] is sorted. Save 2 as the key and compare it with the value immediately to its left.
Shift 5 5 is greater than the key 2, so copy 5 one position right.
Place 2 The key has reached the beginning. Write 2 at index 0; [2, 5] is sorted.
Choose key 4 Save 4 from index 2 and compare it with the rightmost value in the sorted prefix.
Shift 5 again 5 is greater than 4, so move 5 from index 1 to index 2.
Stop at 2 2 is not greater than 4, so no earlier value should move.
Place 4 Write 4 after 2. The sorted prefix becomes [2, 4, 5].
Choose key 1 Save the final value 1. Compare it from right to left against the three-value sorted prefix.
Shift 5 Move 5 right because 5 is greater than 1.
Shift 4 Move 4 right because 4 is also greater than 1.
Shift 2 Move 2 right. The insertion position is now index 0.
Place 1 Write 1 at index 0. Every prefix is now sorted, so the algorithm is complete.

Beating the Bound, and What Libraries Actually Do

Counting sort does not compare. It counts occurrences of each value in a range of size k, then reconstructs the array from the counts, running in O(n + k). When k is small relative to n — sorting a million integers between 0 and 100 — this is linear and unbeatable. When k is large, the count array dominates and the algorithm is useless. It is stable if implemented carefully, using a prefix sum of counts to place elements from the right.

Radix sort applies counting sort to one digit at a time, from least significant to most, giving O(d(n + k)) for d digits. It sorts fixed-width keys — integers, dates, fixed-length strings — in effectively linear time. Its correctness depends entirely on the per-digit sort being stable, since earlier digit orderings must survive later passes.

Bucket sort distributes elements into buckets by value range, sorts each, and concatenates. It is O(n) when the input is uniformly distributed and degrades to O(n²) when everything lands in one bucket.

None of these contradict the lower bound: they exploit structure in the keys rather than comparing, so the decision-tree argument does not apply.

What production libraries use is neither the textbook algorithms nor these — it is hybrids.

Timsort, used by Python's sorted and Java's Arrays.sort for objects, is a stable merge sort that first detects naturally occurring sorted runs in the data and merges them. On already-sorted input it is O(n); on real-world partially-ordered data it is dramatically faster than plain merge sort, which is why it was adopted.

Introsort, used by C++'s std::sort, starts as quicksort, switches to heap sort when the recursion depth exceeds about 2·log n — capping the worst case at O(n log n) — and switches to insertion sort for small partitions. It gets quicksort's speed with heap sort's guarantee.

The practical conclusion: use the library sort. It is a hybrid tuned over years and will beat a hand-written textbook algorithm on real data. Write your own only when you need something the library does not offer — stability where it is not guaranteed, sorting on external storage, or exploiting known key structure with a radix sort.

Counting and radix sort exploit key structure instead of comparing
Radix sort requires a stable per-digit sort to be correct
Timsort detects existing runs — O(n) on sorted input
Introsort is quicksort with a heap sort fallback for the worst case