How do you explain merge sort, and can it run in constant extra space?

Reported as a discussion in a 2023 Computer Science fundamentals hour: design and explain merge sort with constant space complexity, and discuss how the time complexity is logarithmic. The second half of that wording is not correct for the running time, and is worth unpacking carefully.

How standard merge sort works. Split the array into two halves, sort each half, then merge two sorted runs into a buffer with a two-pointer pass. Each merge of a run of length k is O(k). There are O(log n) levels, and each level touches all n elements, so the time is O(n log n), not O(log n). What is logarithmic is the recursion depth, and therefore the call-stack size, which is O(log n). The extra array used for merging is O(n).

Constant extra space. "Constant space merge sort" cannot keep that linear buffer.

• A simple in-place merge inserts each element of the right run into the left run by sliding a gap, using O(1) extra memory besides the call stack. That merge is O(n²) in the worst case, so the sort becomes O(n² log n). It is honest and easy to write in an interview.
• There are more sophisticated in-place merges with better time, but they are rarely something you should try to invent on a whiteboard.
• If the real need is O(n log n) time and O(1) extra memory, heapsort is the usual algorithm to name. It is not merge sort, and it is not stable.

Bottom-up iterative merge sort still needs a linear buffer if each merge is to stay linear-time; dropping the recursion only removes the O(log n) stack.

import java.util.Arrays;

public class MergeSorts {
    static void mergeSort(int[] a) {
        if (a.length < 2) return;
        mergeSort(a, new int[a.length], 0, a.length);
    }

    static void mergeSort(int[] a, int[] buf, int lo, int hi) {
        if (hi - lo < 2) return;
        int mid = (lo + hi) >>> 1;
        mergeSort(a, buf, lo, mid);
        mergeSort(a, buf, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
        while (i < mid) buf[k++] = a[i++];
        while (j < hi) buf[k++] = a[j++];
        System.arraycopy(buf, lo, a, lo, hi - lo);
    }

    /** O(1) extra memory besides the call stack; each merge is quadratic. */
    static void inPlaceMergeSort(int[] a) { inPlaceMergeSort(a, 0, a.length); }

    static void inPlaceMergeSort(int[] a, int lo, int hi) {
        if (hi - lo < 2) return;
        int mid = (lo + hi) >>> 1;
        inPlaceMergeSort(a, lo, mid);
        inPlaceMergeSort(a, mid, hi);
        int i = lo, j = mid;
        while (i < j && j < hi) {
            if (a[i] <= a[j]) i++;
            else {
                int val = a[j];
                System.arraycopy(a, i, a, i + 1, j - i);
                a[i] = val;
                i++;
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2, 8, 0};
        int[] b = a.clone();
        mergeSort(a);
        inPlaceMergeSort(b);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));
    }
}

Verified with OpenJDK 21.0.13: both paths print [0, 1, 2, 4, 5, 8]. The same two sorts were checked against Arrays.sort on random arrays of length 0 through 40; there was no mismatch.

Follow-ups. Stability (standard merge sort is stable; the in-place slide above is also stable; heapsort is not); why the running time is n log n rather than logarithmic; iterator / linked-list merge sort, which can merge with O(1) extra object pointers because the input is already a chain of nodes.