Merge Sort

Merge sort is the first sort in this track that beats O(n²). It does that with a divide-and-conquer strategy: split the array in half, recursively sort each half, then merge the two already-sorted halves back together. The trick that makes it fast is that merging two sorted arrays is cheap — a single linear pass — so all the real work happens in that merge step, and there are only O(log n) levels of splitting.

Divide and Conquer

Three steps, applied recursively:

• Divide: split the array into two halves at the midpoint.
• Conquer: recursively merge-sort each half. The base case is an array of length 0 or 1 — already sorted by definition.
• Combine: merge the two sorted halves into one sorted array.

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;                       // base case: 0 or 1 element, already sorted
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);          // conquer left half
    mergeSort(arr, mid + 1, right);   // conquer right half
    merge(arr, left, mid, right);       // combine
}

Time complexity: O(log n) levels of recursion. Space complexity: O(log n) recursion stack depth for this call alone — the merge() helper below adds the dominant O(n) auxiliary space.

The merge() Helper, Fully Worked

merge() assumes arr[left..mid] and arr[mid+1..right] are each already sorted, and combines them into one sorted run. It copies both halves into a temporary array, then walks two pointers — one per half — always picking the smaller of the two current elements to write back into the original array next.

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;         // pointer into left half
    int j = mid + 1;     // pointer into right half
    int k = 0;            // pointer into temp

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];    // "<=" (not "<") keeps equal elements' original order — this is what makes merge sort stable
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];        // copy any leftover left-half elements
    }
    while (j <= right) {
        temp[k++] = arr[j++];        // copy any leftover right-half elements
    }
    for (int x = 0; x < temp.length; x++) {
        arr[left + x] = temp[x];     // copy merged result back into the original array
    }
}

Time complexity: O(n) — every element from both halves is visited exactly once across the comparison loop and the two cleanup loops combined. Space complexity: O(n) — the temp array holds every element in this range.

Recursion Tree Visualization

Trace merge sort on [8, 3, 7, 4, 2, 6, 1, 5] (8 elements). The array keeps splitting in half until every piece has 1 element, then merges climb back up:

Why O(n log n) Time, O(n) Space

Time complexity: O(n log n) in the best, average, and worst case alike — unlike quick sort (covered next), merge sort's split point is always the midpoint regardless of the data, so there's no unlucky input that makes it degrade. Space complexity: O(n) — the merge() helper allocates a temp array sized to the range being merged, and while these temp arrays don't all exist simultaneously, the largest single allocation (at the top level) is already O(n), plus O(log n) recursion stack depth which is dominated by the O(n) auxiliary array.

Stability

Merge sort is stable: when both halves have equal elements, the merge() code above picks from the left half first (arr[i] <= arr[j], not strictly <), and since the left half always precedes the right half in the original array, equal elements keep their original relative order.

Why It's a Good Default When Stability Matters