Core14 min read

Sorting

From quadratic insertion and selection sorts to O(n log n) merge and quick sort, and the comparison lower bound they all share.

Sorting is the canonical algorithmic problem: easy to state, rich in trade-offs, and a subroutine in countless other tasks from searching to merging. It is also the cleanest place to see asymptotic analysis pay off, because the difference between an $O(n^2)$ and an $O(n \log n)$ sort is exactly what makes large data manageable.

Three families of idea

Quadratic sorts repeatedly find the next element by scanning; merge sort divides the problem in half and combines sorted halves; quicksort partitions around a pivot so that after one pass each side is nearer its final place. Ramanujan-style cleverness is not required — the wins come from dividing.

Run the same array through four sorts below and compare the work each one does.

Race the sorts on one array — compare the work each one does

1 / 5

insertion

20 cmp · 15 swap

selection

28 cmp · 5 swap

bubble

27 cmp · 15 swap

quicksort

15 cmp · 9 swap

Insertion sort is fast on nearly sorted data and O(n^2) when reversed; quicksort partitions around a pivot and averages O(n log n) but can hit its worst case on adversarial input. Selection sort always makes the same number of comparisons. Counts are for this one input, not a proof of the asymptotics.

The quadratic sorts

Insertion sort takes each element and shifts it left into place. It is $O(n)$ when the data is nearly sorted and $O(n^2)$ when reversed, and it wins on small arrays because its constant factor is tiny.
Selection sort finds the minimum of the remaining suffix and swaps it forward. It always performs $\Theta(n^2)$ comparisons regardless of the input.
Bubble sort repeatedly swaps adjacent out-of-order pairs. It is mostly of pedagogical value, though it detects an already-sorted array in one pass.

The divide-and-conquer sorts

Merge sort splits the array in half, sorts each half recursively, then merges two sorted runs in linear time:

$T(n) = 2T(n/2) + O(n) \;\Rightarrow\; T(n) = O(n \log n)$

It is stable and predictable, at the cost of $O(n)$ auxiliary space.

Quicksort partitions around a pivot so smaller elements go left and larger go right, then recurses on both sides. Partitioning is in-place and fast, giving $O(n \log n)$ average time; a poor pivot choice (for example, always the last element on already-sorted data) degrades it to $O(n^2)$ . Randomised or median pivots make that unlikely.

Ask about stability before you sort records

A sort is stable if equal keys keep their original relative order. Merge sort is stable; quicksort and selection sort are not. If you sort a list of people by surname and later by age, stability decides whether each age group stays alphabetised. Python's sorted is stable, so it preserves the previous ordering of ties.

The comparison lower bound

Any sort that only compares pairs of elements needs at least $\Omega(n \log n)$ comparisons in the worst case. There are $n!$ possible orderings, and each comparison yields at most one bit, so a decision tree of depth $d$ can distinguish at most $2^d$ orderings: $2^d \ge n!$ forces $d = \Omega(n \log n)$ . Counting sort and radix sort beat this only by not comparing — they trade memory and key assumptions for linear time.

In practice, Python's sorted is Timsort: merge sort with insertion-sort runs, detecting existing order and staying stable.

Illustrative vs real

The race runs on eight values and counts comparisons and swaps, so the bars and totals come from actual executions. Real inputs range from already-sorted to adversarial, and cache behaviour shapes the constant factor. The asymptotics and the stability distinction are what carry over unchanged.

Check yourself

Eduspheria wiki · Programming & Data Structures, Algorithms

0 / 5 answered

1Which sort is stable and guarantees O(n log n) time?
Multiple choice
2Merge sort on n = 8 elements. How many levels of splitting does the recursion have (including the level of single elements)?
Numeric answer
3Quicksort's worst-case running time is O(n log n).
True / false
4Which property describes a sort that preserves the relative order of equal keys?
Short answer
5Why can counting sort run in linear time while comparison sorts cannot?
Multiple choice

From the mid-term paper

Modeled on NITJ AI-507, Mid-Term October 2024

0 / 5 answered

1Using the Ackermann recursion with A(0, n) = n + 1, A(m, 0) = A(m - 1, 1), and A(m, n) = A(m - 1, A(m, n - 1)) otherwise, what is A(2, 3)?
Numeric answer
2Two mutually recursive functions add the odd and the even digits of a number. What is the sum of the digits of 123456?
Numeric answer
3Merge sort on an array of 16 elements. How many levels of splitting does the recursion have, counting the level of single elements?
Numeric answer
4After a single quicksort partition step around a pivot, which statement is guaranteed?
Multiple choice
5Which asymptotic notation expresses a lower bound on an algorithm's growth?
Short answer

Where next: searching — finding an element, and why sorted data changes the whole game.

The quadratic sorts #

The divide-and-conquer sorts #

The comparison lower bound #

The quadratic sorts

The divide-and-conquer sorts

The comparison lower bound