Three Ways to Sort n Numbers and What They Cost
You are given $n$ distinct numbers in an array. Describe three different algorithms that sort them into increasing order, and analyze the time complexity of each: give the worst-case and average-case running times, and explain where each bound comes from (recurrences, comparison counts, or probabilistic arguments).
Hints
- A natural trio: insertion sort (incremental), merge sort (divide and conquer), quicksort (partition around a pivot). Count comparisons, which dominate the work.
- Insertion sort makes at most $\binom{n}{2}$ comparisons; on a random permutation about half of the pairs are inverted, giving $\Theta(n^2)$ on average too. Merge sort satisfies $T(n) = 2T(n/2) + \Theta(n)$, which the Master theorem solves as $\Theta(n\log n)$.
- For quicksort's average case, note that the $p$-th and $q$-th smallest elements are compared if and only if one of them is the first pivot chosen from the range between them, which has probability $2/(q - p + 1)$. Summing over pairs gives about $2n\ln n$.
Worked Solution
How to Think About It: Every comparison-based sort is a sequence of comparisons, so count them. The three classic strategies are: grow a sorted prefix one element at a time (insertion sort), split the array in half and merge (merge sort), and split around a pivot value (quicksort). The first two have fixed structure so their counts come from direct summation or a recurrence; quicksort's structure depends on the pivots, so its average case needs a probabilistic argument.
Approach: State each algorithm, give code, then derive the bounds: sums of inversions for insertion sort, the Master theorem for merge sort, and pairwise comparison probabilities for quicksort.
Formal Solution:
Algorithm 1 -- Insertion sort. For $i = 2, \dots, n$, take $A[i]$ and shift it left past every larger element in the already sorted prefix $A[1..i-1]$.
```python def insertion_sort(a): for i in range(1, len(a)): key, j = a[i], i - 1 while j >= 0 and a[j] > key: a[j + 1] = a[j] j -= 1 a[j + 1] = key return a ```
*Analysis.* Inserting element $i$ costs up to $i - 1$ comparisons, so the worst case (reverse-sorted input) is $\sum_{i=2}^n (i - 1) = n(n-1)/2 = \Theta(n^2)$. Each shift removes exactly one inversion (a pair $p < q$ with $A[p] > A[q]$), and a uniformly random permutation has $\binom{n}{2}/2 = n(n-1)/4$ inversions on average, so the average case is also $\Theta(n^2)$; the best case (already sorted) is $\Theta(n)$. Space is $O(1)$.
Algorithm 2 -- Merge sort. Split the array into halves, sort each recursively, and merge the two sorted halves in linear time.
```python def merge_sort(a): if len(a) <= 1: return a m = len(a) // 2 left, right = merge_sort(a[:m]), merge_sort(a[m:]) out, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: out.append(left[i]); i += 1 else: out.append(right[j]); j += 1 return out + left[i:] + right[j:] ```
*Analysis.* Merging two sorted lists of total length $n$ takes at most $n - 1$ comparisons, so $T(n) = 2T(n/2) + \Theta(n)$. By the Master theorem with $a = b = 2$, $f(n) = \Theta(n) = \Theta(n^{\log_b a})$, this is $T(n) = \Theta(n\log n)$; unrolling the recursion gives $\log_2 n$ levels each doing $\Theta(n)$ work. The bound holds in the worst, average and best case. It needs $\Theta(n)$ extra space for the merge buffer and is stable.
Algorithm 3 -- Quicksort. Pick a pivot, partition the array into elements smaller and larger than the pivot, and recurse on both sides.
```python import random def quicksort(a): if len(a) <= 1: return a p = a[random.randrange(len(a))] return (quicksort([x for x in a if x < p]) + [x for x in a if x == p] + quicksort([x for x in a if x > p])) ```
*Worst case.* If the pivot is always the smallest or largest element (for example, the first element on already-sorted input), one side is empty and $T(n) = T(n-1) + (n-1)$, so $T(n) = n(n-1)/2 = \Theta(n^2)$.
*Average case.* Label the elements by rank $z_1 < z_2 < \dots < z_n$. Two elements $z_p$ and $z_q$ ($p < q$) are compared at most once, and only if one of them is chosen as pivot before any other element of $\{z_p, \dots, z_q\}$ is; once a pivot strictly between them is chosen they land on different sides and never meet. With random pivots (or random input), each element of that range is equally likely to be the first pivot chosen from it, so $$P(z_p \text{ and } z_q \text{ compared}) = \frac{2}{q - p + 1}.$$ By linearity of expectation the expected number of comparisons is $$E[C_n] = \sum_{p=1}^{n-1}\sum_{q=p+1}^{n}\frac{2}{q - p + 1} = \sum_{p=1}^{n-1}\sum_{k=1}^{n-p}\frac{2}{k+1} \le 2n\,H_n = O(n\log n),$$ and more precisely $E[C_n] = 2(n+1)H_n - 4n \approx 2n\ln n \approx 1.39\,n\log_2 n$. Equivalently, the recurrence $T(n) = (n-1) + \frac{2}{n}\sum_{k=0}^{n-1}T(k)$ solves to the same value. In-place partitioning gives $O(\log n)$ expected extra space; quicksort is not stable.
*Empirical check* (random inputs of size $n = 5000$): insertion sort made about $6.2\times 10^6$ comparisons ($\approx n^2/4$), merge sort about $55{,}000$ ($\approx n\log_2 n = 61{,}000$), quicksort about $72{,}000$ ($\approx 2n\ln n = 85{,}000$).
Answer: Insertion sort: worst and average $\Theta(n^2)$, best $\Theta(n)$, in place. Merge sort: $\Theta(n\log n)$ in every case from $T(n) = 2T(n/2) + \Theta(n)$, but $\Theta(n)$ extra space. Quicksort: worst case $\Theta(n^2)$ with a bad pivot sequence, average $\Theta(n\log n)$ (about $2n\ln n$ comparisons) because elements of rank $p$ and $q$ are compared with probability $2/(q-p+1)$.
Intuition
Sorting is the canonical example of why algorithmic choice matters: insertion sort does $n^2/4$ comparisons on typical input because it fixes one inversion per comparison and a random permutation has $n^2/4$ inversions; merge sort halves the problem and pays linear work to recombine, giving $n\log_2 n$ by the Master theorem; quicksort does the same on average but with in-place partitioning and better constants, at the cost of a $\Theta(n^2)$ worst case that randomized pivots make astronomically unlikely. In quant work these show up when ranking thousands of signals every tick, merging sorted order books, or computing rank correlations, where the difference between $n^2$ and $n\log n$ is the difference between microseconds and milliseconds.