Sorting Algorithms

3.1 Merge Sort

Algorithm. Divide the array in half, recursively sort each half, then merge.

MergeSort(A, l, r):
    if l < r:
        m = (l + r) / 2
        MergeSort(A, l, m)
        MergeSort(A, m+1, r)
        Merge(A, l, m, r)

Theorem 3.1. Merge sort runs in $O(n \log n)$ time in all cases (best, average, worst).

Proof. The recurrence is $T(n) = 2T(n/2) + O(n)$. By the Master theorem (case 2): $a = 2$, $b = 2$, $f(n) = O(n) = O(n^{\log_b a})$So $T(n) = O(n \log n)$. $\blacksquare$

Theorem 3.2. Merge sort is stable and requires $O(n)$ auxiliary space.

Proof of stability. In MergeWhen elements from the left and right halves are equal, we always take from the left half first. This preserves the relative order of equal elements. $\blacksquare$

Theorem 3.3 (Correctness of Merge). The Merge procedure produces a sorted array from two sorted subarrays.

Proof. Let $A[l..m]$ and $A[m+1..r]$ be sorted subarrays. The merge procedure maintains two indices $i$ and $j$ pointing to the next unmerged element in each subarray. At each step, the minimum of $A[i]$ and $A[j]$ is appended to the output. By induction on the number of elements placed: if $k$ elements have been placed and they are the $k$ smallest among the remaining elements, then the $(k+1)$-th element placed is the minimum of the remaining elements. Since each subarray is sorted, the smallest remaining element is $\min(A[i], A[j])$. $\blacksquare$

Theorem 3.4 (Optimality of Merge Sort). Merge sort achieves the optimal $O(n \log n)$ comparison-based sorting bound.

Proof. By Theorem 3.7, no comparison sort can do better than $\Omega(n \log n)$. Merge sort achieves $O(n \log n)$ in all cases, so it is asymptotically optimal among comparison sorts. $\blacksquare$

3.2 Quicksort

Algorithm. Choose a pivot, partition the array into elements $\leq$ pivot and $>$ pivot, recursively Sort each partition.

QuickSort(A, lo, hi):
    if lo < hi:
        p = Partition(A, lo, hi)
        QuickSort(A, lo, p - 1)
        QuickSort(A, p + 1, hi)

Partition (Lomuto): Select the last element as pivot. Iterate through the array, maintaining that elements $A[\mathrm{lo}..i]$ are $\leq$ pivot and $A[i+1..j-1]$ are $>$ pivot.

Theorem 3.5. Quicksort runs in $O(n \log n)$ expected time and $O(n^2)$ worst-case time.

Proof (expected case). If the pivot is chosen uniformly at random, the expected number of Comparisons is $O(n \log n)$ by an indicator random variable argument.

Let $X_{ij}$ be the indicator random variable that $z_i$ and $z_j$ are compared, where $z_1, \ldots, z_n$ are the sorted elements. Since elements are compared only if one is an ancestor of the other in the recursion tree, and the pivot is chosen uniformly at random:

$\mathrm{E}[X_{ij}] = \Pr(z_i \mathrm{~and~} z_j \mathrm{~are~compared}) = \frac{2}{j - i + 1}$

The total number of comparisons is $X = \sum_{i < j} X_{ij}$So:

$\mathrm{E}[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1} \leq \sum_{k=1}^{n} n \cdot \frac{2}{k+1} = O(n \log n)$

Worst case occurs when the pivot is always the smallest or largest element (e.g., already sorted Array with first-element pivot): $T(n) = T(n-1) + O(n) = O(n^2)$. $\blacksquare$

Theorem 3.6. Quicksort is not stable but uses $O(\log n)$ expected stack space.

3.3 Heapsort

Algorithm. Build a max-heap in $O(n)$ time, then repeatedly extract the maximum.

Theorem 3.7. Heapsort runs in $O(n \log n)$ time in all cases, uses $O(1)$ auxiliary space, and Is not stable.

Proof. Building the heap takes $O(n)$ by Theorem 2.11. Each of the $n$ extract-max operations takes $O(\log n)$For a total of $O(n \log n)$. Space is $O(1)$ since the heap is stored in-place. $\blacksquare$

3.4 Lower Bound on Comparison Sorting

Theorem 3.8. Any comparison-based sorting algorithm requires $\Omega(n \log n)$ comparisons in the Worst case.

Proof. A comparison-based sort can be modelled as a decision tree. The tree must have at least $n!$ Leaves (one for each permutation). A binary tree with $n!$ leaves has height at least $\log_2(n!) \geq \log_2((n/2)^{n/2}) = (n/2)\log_2(n/2) = \Omega(n \log n)$.

More precisely, using Stirling”s approximation: $\log_2(n!) = n \log_2 n - n \log_2 e + O(\log n) = \Omega(n \log n)$. $\blacksquare$

3.5 Counting Sort

Counting sort sorts integers in $O(n + k)$ time where $k$ is the range of values.

Algorithm:

1. Count occurrences: $C[i] =$ number of elements equal to $i$.
2. Compute prefix sums: $C[i] =$ number of elements $\leq i$.
3. Place each element in its correct position (iterating backwards for stability).

Theorem 3.9. Counting sort runs in $O(n + k)$ time and $O(n + k)$ space, and is stable.

Proof. Step 1 takes $O(n)$ time. Step 2 takes $O(k)$ time. Step 3 takes $O(n)$ time. The output array uses $O(n)$ space and the count array uses $O(k)$ space. Stability follows from iterating backwards in step 3: the last occurrence of each value is placed first, preserving the order of equal elements. $\blacksquare$

3.6 Radix Sort

Radix sort processes digits from least significant to most significant (LSD radix sort) using a stable sort (e.g., counting sort) as a subroutine.

Theorem 3.10. LSD radix sort sorts $n$ integers with $d$ digits in base $b$ in $O(d(n + b))$ time.

Proof. We perform $d$ passes of counting sort, each taking $O(n + b)$ time. After the $i$-th pass, the array is sorted by the $i$ least significant digits. By induction on $i$After $d$ passes the array is fully sorted. $\blacksquare$

Corollary 3.11. For $d$-digit integers where $d = O(1)$ (e.g., 32-bit integers), radix sort runs in $O(n)$ time.

3.7 External Sorting

Problem. Sort data that is too large to fit in main memory.

Algorithm (External Merge Sort):

1. Read chunks that fit in memory, sort each in memory, write sorted runs to disk.
2. Repeatedly merge runs using a $k$-way merge, reading/writing from disk.

Theorem 3.12. External merge sort with $M$ bytes of memory and $N$ bytes of data performs $O\left(\frac{N}{M} \log_{k}\left(\frac{N}{M}\right)\right)$ passes, where $k$ is the merge fan-in.

Proof. The initial pass creates $N/M$ sorted runs of size $M$. Each merge pass combines $k$ runs into 1, reducing the number of runs by a factor of $k$. After $\log_k(N/M)$ passes, a single sorted run remains. Each pass reads and writes all $N$ bytes, so total I/O is $O(N \log_k(N/M))$. $\blacksquare$

:::caution Common Pitfall The $O(n \log n)$ lower bound applies only to comparison-based sorting. Non-comparison sorts Like radix sort can achieve $O(n)$ time for integers in a bounded range. However, non-comparison sorts sacrifice generality: they depend on the structure of the keys and cannot sort arbitrary objects.

3.8 Comparison of Sorting Algorithms

:::