Merge Sort

Idea

Merge Sort uses divide-and-conquer: split the array into halves, sort each, then merge them into an ordered array.

Algorithm

1. Recursively split into halves until single-element subarrays.
2. Merge pairs of subarrays in order to form sorted sequences.
3. Repeat merging until fully sorted.

Pseudo-code:

function mergeSort(A, left, right):
    if left < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid+1, right)
        merge(A, left, mid, right)

function merge(A, left, mid, right):
    create tmp
    i = left, j = mid+1, k = 0
    while i <= mid and j <= right:
        if A[i] <= A[j]:
            tmp[k++] = A[i++]
        else:
            tmp[k++] = A[j++]
    copy remaining to tmp
    copy tmp back to A[left..right]

Code Implementation

// Merge the two sorted ranges A[left..mid] and A[mid+1..right]
void Merge(int A[], int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = A[left + i];
    for (int j = 0; j < n2; j++) R[j] = A[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) A[k++] = L[i++];
        else A[k++] = R[j++];
    }
    while (i < n1) A[k++] = L[i++];  // copy what is left
    while (j < n2) A[k++] = R[j++];
}

void MergeSort(int A[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        MergeSort(A, left, mid);         // sort the left half
        MergeSort(A, mid + 1, right);    // sort the right half
        Merge(A, left, mid, right);      // merge the two halves
    }
}

Natural Merge Sort

Unlike the standard merge, which always splits the sequence in half, natural merge first scans the sequence to find the runs that are already ordered and merges those runs directly. This reduces the number of merge passes and is especially well suited to data that is already locally ordered.

Complexity

• Best/worst/avg: $O(n\log n)$
• Space: $O(n)$
• Stability: stable

Exercises

Exercise 1

Run merge sort on $A = [8, 4, 5, 7, 1, 3, 6, 2]$; show the first merge result.

Exercise 2

What are merge sort’s time and space complexities?