Sorting & Searching

Mergesort

A divide-and-conquer sort with a guaranteed O(n log n) worst case and stable ordering — the price is an auxiliary array the size of the input, since merging cannot be done in place efficiently.

Split the array in half, sort each half recursively, merge the two sorted halves
Guaranteed O(n log n) worst case — no adversarial input degrades it, unlike Quicksort
Stable: equal elements keep their relative order, because merge always takes from the left run on ties
Needs Θ(n) auxiliary space for the merge step — not in-place
Top-down (recursive) and bottom-up (iterative, merging runs of size 1, 2, 4, …) are equivalent in complexity

Top-down mergesort

static void mergeSort(int[] a, int[] aux, int lo, int hi) {
    if (hi - lo < 2) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, aux, lo, mid);
    mergeSort(a, aux, mid, hi);
    merge(a, aux, lo, mid, hi);
}

static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
    System.arraycopy(a, lo, aux, lo, hi - lo);
    int i = lo, j = mid;
    for (int k = lo; k < hi; k++) {
        if (i >= mid) a[k] = aux[j++];
        else if (j >= hi) a[k] = aux[i++];
        else if (aux[j] < aux[i]) a[k] = aux[j++];   // < , not <=, keeps it stable
        else a[k] = aux[i++];
    }
}

Mergesort vs quicksort vs heapsort
	Mergesort	Quicksort	Heapsort
Worst case	O(n log n)	O(n²)	O(n log n)
Extra space	O(n)	O(log n) stack	O(1)
Stable	yes	no	no
Cache behavior	good (sequential merges)	excellent	poor (heap access pattern)