Merge Sort

Sorting O(n log n) O(n)

Recursively splits the array in half, sorts each half, then merges the two sorted halves back together.

Idle

Starting Merge Sort on 8 elements.

InvariantBoth halves being merged are already sorted, so the smaller of the two heads is the smallest value left.

1/57

comparisons0moves0lo0mid0hi0

compareswapshiftselectsorted

merge-sort.c

void merge(int arr[], int lo, int mid, int hi) {
    int n1 = mid - lo + 1, n2 = hi - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[lo + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
 
    int i = 0, j = 0, k = lo;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}
 
void mergeSort(int arr[], int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

How Merge Sort works

Split the array in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front element. All the real work happens in the merge.

Best case

Always O(n log n) — the split/merge structure does not depend on the data.

Worst case

Still O(n log n), but needs O(n) scratch space for merging.

When to use it

Stable sorting, linked lists, external sorting of data too big for memory, and guaranteed bounds.