The Mathematics of Sorting Algorithms

Sorting is one of the most studied problems in computer science, because almost everything else, from searching a phone contact list to ranking exam results, becomes easier once the data is in order. Behind every sorting algorithm sits some elegant mathematics: summation formulas, logarithms, permutations and a beautiful proof that sets a hard speed limit no clever programmer can break. Let's work through it.

Measuring a Sorting Algorithm

When we analyse a sort, we usually count comparisons (questions like "is \(a_i < a_j\)?") and sometimes swaps or moves. We express these counts as functions of \(n\), the number of items, and then describe their growth with Big-O notation. Three questions matter:

• How many comparisons in the worst case?
• How many on average, over all possible input orders?
• How much extra memory does it need?

Quadratic Sorts: Bubble, Selection and Insertion

Bubble sort and selection sort

Bubble sort repeatedly passes through the list and swaps neighbours that are out of order. On the first pass it makes \(n - 1\) comparisons, on the second \(n - 2\), and so on down to 1. Selection sort, which finds the smallest remaining element each time, has exactly the same comparison count:

$$ (n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2} $$

For \(n = 10\) that is \(\frac{10 \times 9}{2} = 45\) comparisons. Since \(\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}\), these algorithms are \(O(n^2)\).

Inversions and insertion sort

An inversion is a pair of positions \(i < j\) where \(a_i > a_j\), meaning the pair is in the wrong order. A sorted list has 0 inversions; a list in exact reverse order has the maximum, \(\frac{n(n-1)}{2}\), because every pair is wrong.

Insertion sort, and bubble sort's swaps, fix exactly one inversion per swap of neighbours, so the number of swaps equals the number of inversions. On a random list, any given pair is equally likely to be in either order, so the expected number of inversions is half the maximum:

$$ E[\text{inversions}] = \frac{1}{2} \cdot \frac{n(n-1)}{2} = \frac{n(n-1)}{4} $$

This proves that any algorithm that only swaps neighbours is \(O(n^2)\) on average. To go faster, an algorithm must move elements long distances in one step.

Worked Example 1: Counting Inversions

Count the inversions in the list \([5, 2, 8, 1, 9, 3, 7, 4]\), and hence the number of swaps insertion sort will make.

Step 1: For each element, count the smaller elements to its right.

• 5: smaller elements to its right are 2, 1, 3, 4, giving 4
• 2: only 1, giving 1
• 8: 1, 3, 7, 4, giving 4
• 1: none, giving 0
• 9: 3, 7, 4, giving 3
• 3: none, giving 0
• 7: 4, giving 1
• 4: nothing to its right, giving 0

Step 2: Add them: \(4 + 1 + 4 + 0 + 3 + 0 + 1 + 0 = 13\).

Step 3: Interpret. Insertion sort will perform exactly 13 neighbour swaps. Sanity check: the maximum possible for \(n = 8\) is \(\frac{8 \times 7}{2} = 28\) and the random-order average is 14, so 13 is entirely reasonable for a shuffled list.

Divide and Conquer: Merge Sort

Merge sort splits the list in half, sorts each half recursively, and then merges the two sorted halves. Merging two sorted lists with a total of \(m\) elements takes at most \(m - 1\) comparisons, because each comparison places one element into the output and the last element needs no comparison.

The running time satisfies the recurrence

$$ T(n) = 2T\!\left(\frac{n}{2}\right) + n $$

The recursion tree has \(\log_2 n\) levels, and the merges on each level handle \(n\) elements in total, so

$$ T(n) = \Theta(n \log n) $$

Worked Example 2: Merge Sort Step by Step

Sort \([5, 2, 8, 1, 9, 3, 7, 4]\) with merge sort and count comparisons.

Level 1 (merge pairs): \([5,2] \to [2,5]\), \([8,1] \to [1,8]\), \([9,3] \to [3,9]\), \([7,4] \to [4,7]\). That is 4 comparisons.

Level 2 (merge pairs of pairs):

• Merge \([2,5]\) and \([1,8]\): compare 2 vs 1 (take 1), 2 vs 8 (take 2), 5 vs 8 (take 5), then 8 is left. Result \([1,2,5,8]\), 3 comparisons.
• Merge \([3,9]\) and \([4,7]\): 3 vs 4 (take 3), 9 vs 4 (take 4), 9 vs 7 (take 7), then 9. Result \([3,4,7,9]\), 3 comparisons.

Level 3 (final merge): merge \([1,2,5,8]\) with \([3,4,7,9]\):

1. 1 vs 3, take 1
2. 2 vs 3, take 2
3. 5 vs 3, take 3
4. 5 vs 4, take 4
5. 5 vs 7, take 5
6. 8 vs 7, take 7
7. 8 vs 9, take 8, then 9 is left over

That is 7 comparisons, giving \([1,2,3,4,5,7,8,9]\).

Total: \(4 + 6 + 7 = 17\) comparisons. Compare this with 28 for bubble sort on 8 items, and with \(n \log_2 n = 8 \times 3 = 24\), which is the upper bound we expect. The gap grows dramatically: for one million items, bubble sort needs about \(5 \times 10^{11}\) comparisons while merge sort needs roughly \(2 \times 10^7\), about 25,000 times fewer.

The Speed Limit: Why n log n Is the Best Possible

Can a cleverer comparison-based algorithm beat \(n \log n\)? Remarkably, no, and the proof uses counting.

Any comparison sort can be drawn as a decision tree: each internal node is a comparison with two outcomes, and each leaf is a final ordering. The input could be any of the \(n!\) permutations, and each needs its own leaf. A binary tree of height \(h\) has at most \(2^h\) leaves, so

$$ 2^h \geq n! \implies h \geq \log_2(n!) $$

Using Stirling's approximation, \(\log_2(n!) \approx n \log_2 n - 1.44n\), which is \(\Theta(n \log n)\). Therefore every comparison sort needs \(\Omega(n \log n)\) comparisons in the worst case, and merge sort and heap sort are optimal up to constant factors.

Example: to sort 4 items, \(4! = 24\) orderings and \(\log_2 24 \approx 4.58\), so at least 5 comparisons are needed in the worst case. For 10 items, \(\log_2(3{,}628{,}800) \approx 21.79\), so at least 22 comparisons.

Breaking the Limit Without Comparisons

The lower bound only applies to algorithms that compare elements. Counting sort sorts integers in the range 0 to \(k\) by counting how many times each value appears, taking \(O(n + k)\) time. Radix sort applies this digit by digit. When the keys are small integers, such as exam marks out of 100, these run in linear time.

Quicksort and Probability

Quicksort picks a pivot, partitions the list around it, and recurses. A bad pivot every time gives \(O(n^2)\), but with random pivots the expected number of comparisons is about \(2n \ln n \approx 1.39\, n \log_2 n\). Its small constant factors make it one of the fastest sorts in practice.

Did You Know?

• John von Neumann described merge sort around 1945, making it one of the earliest algorithms written for a stored-program computer.
• Tony Hoare invented quicksort in 1959 while working on machine translation in Moscow.
• Python's built-in sort, Timsort (2002), combines merge sort and insertion sort and runs in linear time on data that is already nearly sorted.

Key Takeaways

• Bubble, selection and insertion sort use about \(\frac{n^2}{2}\) comparisons, so they are \(O(n^2)\).
• The number of inversions equals the number of neighbour swaps needed, averaging \(\frac{n(n-1)}{4}\).
• Merge sort's recurrence \(T(n) = 2T(n/2) + n\) gives \(\Theta(n \log n)\).
• The decision-tree argument proves no comparison sort can beat \(\log_2(n!) = \Theta(n \log n)\).
• Non-comparison sorts like counting sort can be linear for small integer keys.

For step-by-step help with algorithm analysis, sorting proofs or programming assignments, contact Amathify's experts and PhD scholars via WhatsApp or the Ask a Question form.