Skip to main content

Merge sort algorithm and trace

Short answer

Merge sort divides the array into halves recursively, then merges sorted halves. For 5,2,4,6,1,3,2,6: splitting yields single elements. Merging pairs: [5]&[2]→2,5; [4]&[6]→4,6; [1]&[3]→1,3; [2]&[6]→2,6. Merging halves: [2,5]&[4,6]→2,4,5,6; [1,3]&[2,6]→1,2,3,6. Final merge: 1,2,2,3,4,5,6,6.

Discuss the algorithm merge sort. Show the steps to sort the data 5, 2, 4, 6, 1, 3, 2, 6 using merge sort.

Merge sort is a divide-and-conquer sorting algorithm. It divides the array into two halves, sorts each half recursively, and merges the two sorted halves into one sorted array.

Algorithm

MERGESORT(a, low, high)
1. if low < high
2.     mid = (low + high) / 2
3.     MERGESORT(a, low, mid)          // sort left half
4.     MERGESORT(a, mid+1, high)       // sort right half
5.     MERGE(a, low, mid, high)        // combine

MERGE copies the smaller of the two front elements into a temporary array, repeatedly, until one half is exhausted, then copies the rest of the other half, and finally copies the temporary array back.

void merge(int a[], int lo, int mid, int hi) {
    int t[100], i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi)
        t[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) t[k++] = a[i++];
    while (j <= hi)  t[k++] = a[j++];
    for (k = 0, i = lo; i <= hi; i++, k++) a[i] = t[k];
}
void mergeSort(int a[], int lo, int hi) {
    if (lo < hi) {
        int mid = (lo + hi) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }
}

Complexity: T(n) = 2T(n/2) + O(n), so best, average and worst cases are all O(n log n). It needs O(n) extra space and is stable.

Trace for 5, 2, 4, 6, 1, 3, 2, 6

5 2 4 6 1 3 2 6
5 2 4 6 | 1 3 2 6
5 2 | 4 6 | 1 3 | 2 6
5 | 2 | 4 | 6 | 1 | 3 | 2 | 6
StepMergeResult
1[5] + [2][2, 5]
2[4] + [6][4, 6]
3[1] + [3][1, 3]
4[2] + [6][2, 6]
5[2, 5] + [4, 6][2, 4, 5, 6]
6[1, 3] + [2, 6][1, 2, 3, 6]
7[2, 4, 5, 6] + [1, 2, 3, 6][1, 2, 2, 3, 4, 5, 6, 6]

Answer: 1, 2, 2, 3, 4, 5, 6, 6

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 7 questions →