Question 5 of 8: Sorting

Question 5: Sorting (10 marks: 3, 4, 3)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

1. Trace on [5,8,1,4,7,2,3,9,5] — 3 marks

Merge sort recursively splits the array in half until single elements remain, then merges pairs of already-sorted runs back together in order.

1. Divide. $[5,8,1,4,7,2,3,9,5] \to [5,8,1,4]\;|\;[7,2,3,9,5]$, then each half again: $[5,8]\,|\,[1,4]$ and $[7,2]\,|\,[3,9,5]$, and once more: $[5]\,|\,[8]$, $[1]\,|\,[4]$, $[7]\,|\,[2]$, $[3]\,|\,[9,5]\to[9]\,|\,[5]$ — recursion bottoms out at 9 single-element runs.
2. Merge upward, level by level. $[5],[8]\to[5,8]$; $[1],[4]\to[1,4]$; $[7],[2]\to[2,7]$; $[9],[5]\to[5,9]$, then $[3],[5,9]\to[3,5,9]$.
3. Merge the two big halves. $[5,8]$ and $[1,4]$ merge to $[1,4,5,8]$; $[2,7]$ and $[3,5,9]$ merge to $[2,3,5,7,9]$.
4. Final merge. Merging $[1,4,5,8]$ with $[2,3,5,7,9]$ by repeatedly taking the smaller front element (ties keep the left run's copy, so the algorithm is stable): $1,2,3,4,5,5,7,8,9$ — the two original 5's both survive. $$\boxed{[1,2,3,4,5,5,7,8,9]}$$

2. Recursive implementation — 4 marks

void merge(int a[], int lo, int mid, int hi) {
    int n1 = mid - lo + 1, n2 = hi - mid;
    int *L = malloc(n1 * sizeof(int)), *R = malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++) L[i] = a[lo + i];
    for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];

    int i = 0, j = 0, k = lo;
    while (i < n1 && j < n2)
        a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];   /* <= keeps it stable */
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
    free(L); free(R);
}

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

3. Asymptotic complexity — 3 marks

Approach. Write the recurrence for the work done, then solve it (recursion-tree or Master theorem).

1. Set up the recurrence. Splitting the array costs $O(1)$, two recursive calls each handle $n/2$ elements, and merging two sorted halves back together costs $O(n)$ (one linear scan): $$T(n) = 2T(n/2) + O(n), \qquad T(1) = O(1).$$
2. Solve by recursion tree. At recursion depth $k$ there are $2^k$ subproblems of size $n/2^k$, each contributing $O(n/2^k)$ merge work, so every level costs $O(n)$ in total regardless of depth. The tree has $\log_2 n$ levels (halving $n$ down to 1), so $$T(n) = O(n)\cdot\log_2 n = \boxed{O(n\log n)}.$$
3. Cross-check via the Master theorem. $T(n)=aT(n/b)+f(n)$ with $a=2,\,b=2,\,f(n)=O(n)$; since $f(n)=\Theta(n^{\log_b a}) = \Theta(n^1)$, this is Master-theorem Case 2, giving $T(n)=\Theta(n\log n)$ directly — matching the recursion-tree result. This bound holds for the best, average, and worst case alike, since the split is always exactly in half regardless of input order.