algorithms · high

Merge Sort

Merge sort divides the array down to single elements then merges sorted runs back together. It is O(n log n) in the best, average, and worst case and is stable, at the cost of O(n) auxiliary space for merging. Because it accesses data sequentially, it's the standard choice for linked lists and for external (on-disk) sorting.

The code

void merge(int a[], int lo, int mid, int hi); // merge two sorted halves

void mergeSort(int a[], int lo, int hi) {
    if (lo >= hi)
        return; // 0 or 1 element: sorted
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);     // sort the left half
    mergeSort(a, mid + 1, hi); // sort the right half
    merge(a, lo, mid, hi);     // merge them back together
}

What this lesson walks through

1. 01Merge sort — divide and conquer
2. 02Merge runs of width 1
3. 03Merge runs of width 2
4. 04Merge runs of width 4
5. 05Sorted

Merge sort splits the array down to single elements (each trivially sorted), then merges sorted runs back together. Shown bottom-up: merge runs of width 1, then 2, then 4.