Merge sort

Split the array in half, sort each half, then merge the two sorted halves. Divide and conquer.

Time O(n log n)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A one-element array is sorted. Merging two sorted arrays takes linear time: keep taking the smaller front element. Halving gives log n levels, each doing n work.

Code

C++PythonC#

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> left(a.begin() + lo, a.begin() + mid + 1), right(a.begin() + mid + 1, a.begin() + hi + 1);
    int i = 0, j = 0;
    for (int k = lo; k <= hi; k++) {
        if (j >= (int)right.size() || (i < (int)left.size() && left[i] <= right[j]))
            a[k] = left[i++];
        else
            a[k] = right[j++];
    }
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

def merge_sort(a: list[int], lo: int, hi: int) -> None:
    if lo >= hi: return
    mid = (lo + hi) // 2
    merge_sort(a, lo, mid)
    merge_sort(a, mid + 1, hi)
    merge(a, lo, mid, hi)

def merge(a: list[int], lo: int, mid: int, hi: int) -> None:
    left, right = a[lo:mid + 1], a[mid + 1:hi + 1]
    i = j = 0
    for k in range(lo, hi + 1):
        if j >= len(right) or (i < len(left) and left[i] <= right[j]):
            a[k] = left[i]; i += 1
        else:
            a[k] = right[j]; j += 1

public static void MergeSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    MergeSort(a, lo, mid);
    MergeSort(a, mid + 1, hi);
    Merge(a, lo, mid, hi);
}

static void Merge(int[] a, int lo, int mid, int hi) {
    int[] left = a[lo..(mid + 1)], right = a[(mid + 1)..(hi + 1)];
    int i = 0, j = 0;
    for (int k = lo; k <= hi; k++) {
        if (j >= right.Length || (i < left.Length && left[i] <= right[j]))
            a[k] = left[i++];
        else
            a[k] = right[j++];
    }
}

Tips

Guaranteed O(n log n) and stable, at the cost of O(n) extra memory.
The merge step alone is a classic: merge two sorted lists, count inversions, external sorting.

In the .NET library

LINQ OrderBy is a stable sort. Array.Sort is not. Reach for OrderBy when equal items must keep their original order.