Sorting algorithms: analysis, lower bound, counting and radix sort

At the end of SEN2211 you saw the simple $O(n^2)$ sorts such as bubble, selection and insertion sort. In this course the questions go one level up. The exam has three kinds of questions: trace (what are the halves before the merge, what is the array after the first partition, what is the heap after buildHeap), analyze (best, average, worst case, how many comparisons), compare (which is stable, which is in place, which one to use when).

Golden rules:

1. Merge sort is $O(n \log n)$ in every case, but it needs $O(n)$ extra memory.
2. Quicksort is the fastest on average, but with bad pivots it becomes $O(n^2)$.
3. Heapsort is $O(n \log n)$ in every case and in place, but it is not stable.
4. No comparison-based sort can beat $\Omega(n \log n)$ in the worst case.
5. Counting and radix sort beat this bound, because they make no comparisons; they put extra assumptions on the keys.

Merge sort

Divide and conquer. Split the array in the middle, sort the two halves recursively, then merge the two sorted halves in a single pass. The merge step looks at the head of both lists and writes the smaller one to the output.

static void mergeSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;          // 0 or 1 element: already sorted
    int mid = (lo + hi) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);         // O(hi - lo + 1)
}

For [42, 17, 8, 93, 25, 61, 4, 30], the order of merge calls (each line is the state of that range after one merge):

merge [0..1] -> [17, 42]
merge [2..3] -> [8, 93]
merge [0..3] -> [8, 17, 42, 93]
merge [4..5] -> [25, 61]
merge [6..7] -> [4, 30]
merge [4..7] -> [4, 25, 30, 61]
merge [0..7] -> [4, 8, 17, 25, 30, 42, 61, 93]
toplam karşılaştırma: 17

Note: you do not move to the right half until the left half is completely done. For “which is the second merge?” the answer is [2..3], not [4..5].

Analysis

The recurrence:

$T(n) = 2T(n/2) + cn, \qquad T(1) = c$

At every level of the recursion tree the total work is $cn$, and there are $\log_2 n$ levels. The result is $T(n) = O(n \log n)$. This time does not depend on the input: sorted, reverse sorted and random inputs all take the same. The extra memory is $O(n)$, because merge uses a temporary array.

Quicksort

Choose a pivot. Partition the array so that elements smaller than the pivot go to the left and larger ones go to the right. The pivot is now in its final place. Sort both sides recursively. There is no merge step; the work is in the partition.

On this page we use the Lomuto scheme: the pivot is the last element, and i marks the end of the “smaller” region.

static int partition(int[] a, int lo, int hi) {
    int p = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < p) { i++; swap(a, i, j); }
    swap(a, i + 1, hi);            // pivot to its place
    return i + 1;
}

Full trace on [29, 71, 12, 55, 8, 40, 33]:

partition [0..6] pivot=33 -> [29,12,8,33,71,40,55]
partition [0..2] pivot=8  -> [8,12,29,33,71,40,55]
partition [1..2] pivot=29 -> [8,12,29,33,71,40,55]
partition [4..6] pivot=55 -> [8,12,29,33,40,55,71]

In the first partition, 29, 12 and 8 were collected at the front because they are smaller than the pivot; 33 landed at index 3 and never moved again.

Analysis

In the worst case the recurrence is $T(n) = T(n-1) + cn$, for a total of $n(n-1)/2$ comparisons. With the last element as pivot, an already sorted array produces exactly this case. Practical fixes: a random pivot or median-of-three (the median of the first, middle and last elements). Switching to insertion sort for small subarrays (around n < 10) is also common.

PITFALL · “quicksort is always n log n”. It is not. The average and best cases are $O(n \log n)$, the worst case is $O(n^2)$. If the exam asks for “worst case”, the answer is $O(n^2)$.

Heapsort

We will cover heaps in detail in week 7. For now you only need to know this: a max-heap is a complete binary tree in which every node is greater than or equal to its children, and it is stored in an array. In a 0-indexed array the children of i are 2i+1 and 2i+2.

Heapsort has two phases:

1. buildHeap: from the last internal node (n/2 - 1) up to the root, percolate each node down. Time $O(n)$.
2. n - 1 times deleteMax: swap the root (the largest) with the last element of the heap, reduce the heap size by 1, and percolate the new root down. Each takes $O(\log n)$.

For [6, 3, 9, 1, 8, 2]:

buildHeap   -> [9, 8, 6, 1, 3, 2]
deleteMax 1 -> [8, 3, 6, 1, 2 | 9]
deleteMax 2 -> [6, 3, 2, 1 | 8, 9]
deleteMax 3 -> [3, 1, 2 | 6, 8, 9]
deleteMax 4 -> [2, 1 | 3, 6, 8, 9]
deleteMax 5 -> [1 | 2, 3, 6, 8, 9]

The part to the right of the | mark is the sorted region. With a max-heap the array ends up in ascending order, because each step writes the largest element to the end. The total time is $O(n \log n)$ in every case, and the extra memory is $O(1)$.

The lower bound for comparison-based sorting

Any algorithm that works only with comparisons like a[i] < a[j] can be drawn as a decision tree. Each internal node is a comparison, and each leaf is one ordering (permutation) of the input.

• For n distinct elements there are $n!$ possible orderings. The algorithm must tell them all apart: at least $n!$ leaves.
• A binary tree of height $h$ has at most $2^h$ leaves.
• $2^h \ge n! \Rightarrow h \ge \log_2(n!)$.
• By Stirling’s approximation, $\log_2(n!) = \Theta(n \log n)$.

The height of the tree is the number of comparisons in the worst case. The result:

$\text{worst-case comparisons} \ge \lceil \log_2 n! \rceil = \Omega(n \log n)$

This is why merge sort and heapsort are asymptotically optimal comparison-based sorts.

Counting sort

If the keys are integers in 0..k, you can sort without comparisons. Count how many times each value occurs, use prefix sums to find each value’s position in the output, and place the input items by scanning from right to left.

[2, 5, 3, 0, 2, 3, 0, 3], k = 5:

count  = [2, 0, 2, 3, 0, 1]
prefix = [2, 2, 4, 7, 7, 8]
output = [0, 0, 2, 2, 3, 3, 3, 5]

prefix[3] = 7 means: the last 3 goes to index 6 (7 - 1) of the output. The counter drops by one at each placement. Scanning from right to left preserves the order of equal keys: the sort is stable. Time is $O(n + k)$, memory is $O(n + k)$. It is impractical when k is very large (e.g. 32-bit numbers).

Radix sort

Sort multi-digit numbers starting from the least significant digit (LSD), using a stable bucket/counting pass for each digit.

[329, 457, 657, 839, 436, 720, 355]:

ones     -> [720, 355, 436, 457, 657, 329, 839]
tens     -> [720, 329, 436, 839, 355, 457, 657]
hundreds -> [329, 355, 436, 457, 657, 720, 839]

In the second pass, 720 and 329 both have tens digit 2, so they are in the same bucket. They kept their order from the first pass (720 first). Every pass must be stable, otherwise the work of the earlier digits is lost.

Time: for d digits and base b, $O(d(n + b))$. If d and b are constants, it is linear.

Summary table

Common mistakes

static void merge(int[] a, int lo, int mid, int hi) {
    int[] tmp = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    for (k = 0; k < tmp.length; k++) a[lo + k] = tmp[k];
}