Merge sort

Merge sort is a divide-and-conquer sorting algorithm. Recursively split the array in half, sort each half, then merge the two sorted halves into one sorted result. Runs in $O (n lo g n)$ in all cases (best, average, worst), is stable, but uses $O (n)$ extra space.

The structure:

Divide: split the array into two halves.
Conquer (recur): sort each half.
Combine (merge): merge the two sorted halves into a single sorted array.

The base case is a sub-array of size 1, which is trivially sorted.

The merging step

Merging two sorted arrays into one sorted array is the heart of merge sort:

Input: A = [3, 7, 12], B = [5, 8, 15]
Output: C = [3, 5, 7, 8, 12, 15]

Walk through both with separate indices, taking the smaller front element at each step:

indexA = 0, indexB = 0, indexC = 0
A[0]=3, B[0]=5  → take A: C[0]=3, indexA=1
A[1]=7, B[0]=5  → take B: C[1]=5, indexB=1
A[1]=7, B[1]=8  → take A: C[2]=7, indexA=2
A[2]=12, B[1]=8 → take B: C[3]=8, indexB=2
A[2]=12, B[2]=15 → take A: C[4]=12, indexA=3 (done with A)
B[2]=15 remaining → C[5]=15

When one input is exhausted, drain the other into C. Each element gets compared to one element of the other array (or fewer); merging is $O (∣ A ∣ + ∣ B ∣)$ .

void merge(int arr[], int tempArr[], int first, int midpt, int last) {
    int indexA = first;
    int indexB = midpt;
    int indexC = first;
    
    while (indexA < midpt && indexB < last) {
        if (arr[indexA] < arr[indexB]) {
            tempArr[indexC++] = arr[indexA++];
        } else {
            tempArr[indexC++] = arr[indexB++];
        }
    }
    
    while (indexA < midpt)  tempArr[indexC++] = arr[indexA++];
    while (indexB < last)   tempArr[indexC++] = arr[indexB++];
    
    for (int i = first; i < last; i++) {
        arr[i] = tempArr[i];
    }
}

The recursive partition

void msort(int arr[], int tempArr[], int first, int last) {
    if (first + 1 < last) {
        int midpt = (first + last) / 2;
        msort(arr, tempArr, first, midpt);
        msort(arr, tempArr, midpt, last);
        if (arr[midpt - 1] <= arr[midpt]) return;   // already sorted
        merge(arr, tempArr, first, midpt, last);
    }
}

The early-exit if (arr[midpt - 1] <= arr[midpt]) return; is an optimization — if the left half’s last element is already ≤ the right half’s first, the merge is a no-op.

Big O

Each level of recursion does $O (n)$ work (merging across the array).
Recursion depth is $O (lo g n)$ (halving each time).
Total: $O (n lo g n)$ .

This holds for all inputs — no input pattern can degrade merge sort. Compare to quicksort which has $O (n^{2})$ worst case.

Properties

Stable: yes. Equal elements preserve relative order (the merge step takes from the left half first when elements are equal).
In place: no. Requires $O (n)$ extra space for tempArr.
Predictable: same time on any input.

When to use

Merge sort is the right choice when:

Stability matters. Sorting records by one field while preserving order from another.
Worst-case performance matters. Real-time systems can’t tolerate quicksort’s $O (n^{2})$ degenerate cases.
External sorting (data doesn’t fit in memory). Merge sort naturally handles streaming — read sorted chunks, merge them. Used by databases for sorting on disk.

When in-memory cache behavior matters more, Quick sort usually wins on real workloads. When $O (1)$ extra space matters, Heap sort.

Variants

Top-down (the version above): recurse, then merge.
Bottom-up: iteratively merge size-1 chunks into size-2, then size-4, etc.
Timsort: hybrid merge sort + insertion sort, used by Python and Java’s Arrays.sort for objects. Adaptive to existing runs of sorted data.

For the in-place divide-and-conquer alternative, see Quick sort. For O(n log n) without extra space, see Heap sort.

Idriss Rami — Notes

Explorer