Question 6 of 7: Merge Sort

Question 6: Merge Sort (20 marks: 4 items, 5 marks each)

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.

Given. Two already-sorted input arrays (for the merge step) and the unsorted array $[9,5,2,6,1,7,8,3]$ (for the full sort). Find. a merge procedure, a description of the recursive Merge Sort algorithm, and its trace on the 8 given values.

1. Merging two sorted lists — 5 marks

Merging combines two already-sorted lists into one sorted list by repeatedly comparing the two lists' current front elements and moving the smaller one (or either, on a tie) to the output, advancing only the list that element came from. Once one list is exhausted, the remainder of the other list is copied across unchanged, since everything left in it is already known to be no smaller than everything already output. A merge of two lists of total length $n$ does exactly $n-1$ comparisons in the worst case and runs in $O(n)$ time and $O(n)$ extra space.

2. merge() implementation — 5 marks

void merge(int a[MAX], int b[MAX], int c[MAX + MAX], int na, int nb) {
    int i = 0, j = 0, k = 0;
    while (i < na && j < nb)
        c[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];  /* <= keeps the merge stable */
    while (i < na) c[k++] = a[i++];
    while (j < nb) c[k++] = b[j++];
}

3. The Merge Sort algorithm — 5 marks

Merge Sort is a divide-and-conquer algorithm: it splits the input array into two halves, recursively sorts each half independently (a base case of size 0 or 1 is already sorted), and then merges the two now-sorted halves back into one fully sorted array using the merge procedure above. Because the split is always into two roughly equal halves, the recursion has depth $O(\log n)$, and each of those $O(\log n)$ levels does $O(n)$ total work merging, giving $O(n\log n)$ overall.

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

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

Approach. Split repeatedly in half down to single elements, then merge pairs of sorted runs back together, level by level.

1. Divide. $[9,5,2,6,1,7,8,3] \to [9,5,2,6]\,|\,[1,7,8,3]$, then $[9,5]\,|\,[2,6]$ and $[1,7]\,|\,[8,3]$, then to 8 single-element runs — recursion bottoms out.
2. Merge level 1 (pairs of singles). $[9],[5]\to[5,9]$; $[2],[6]\to[2,6]$; $[1],[7]\to[1,7]$; $[8],[3]\to[3,8]$.
3. Merge level 2 (pairs of 2-runs). $[5,9]$ and $[2,6]$ merge to $[2,5,6,9]$; $[1,7]$ and $[3,8]$ merge to $[1,3,7,8]$.
4. Final merge. Merging $[2,5,6,9]$ with $[1,3,7,8]$ by repeatedly taking the smaller front element: $$\boxed{[1,2,3,5,6,7,8,9]}$$