Implement Merge-sort in-place

The problem, simply

Merge sort splits an array into halves, sorts each half, and merges the two sorted halves. The usual merge copies numbers into a helper array of size n, so it needs O(n) extra room.

Write merge sort whose merge step works in place: no helper array, only a few extra variables (the waiting calls of the recursion are allowed). The result must be the array sorted from small to big.

A story to remember it

Picture it

Examples

Way 1: the simple way

Merge by sliding. Keep finger i in the left half and j at the start of the right half.

1. If arr[i] <= arr[j], arr[i] is in the right place. Move i.
2. Otherwise arr[j] must go to position i. Save it, slide everything from i to j - 1 one step right, and drop it at i. The left half is now one longer, so move i, mid and j all by one.
3. Stop when either half is used up.

class Solution {
    private void merge(int[] arr, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        if (arr[mid] <= arr[j]) return;         // already in order
        while (i <= mid && j <= hi) {
            if (arr[i] <= arr[j]) {
                i++;                            // arr[i] is in place
            } else {
                int value = arr[j];
                for (int k = j; k > i; k--) arr[k] = arr[k - 1];   // slide right
                arr[i] = value;                 // drop the small one in the hole
                i++;
                mid++;
                j++;
            }
        }
    }

    public void mergeSort(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(arr, lo, mid);
        mergeSort(arr, mid + 1, hi);
        merge(arr, lo, mid, hi);
    }
}

How long it takes: one merge of L numbers can slide about L * L / 4 times (think of a backwards array). Adding that up over all merges gives O(n^2), the same as insertion sort. Extra room: only the waiting calls, O(log n). It keeps equal numbers in their original order.

Way 2: the clever way

Merge with shrinking gaps, the same idea as Shell sort. The two halves are already sorted, so a few passes are enough.

1. Let L be the length of the stretch being merged. Start with gap = ceil(L / 2).
2. Walk i from the start: compare arr[i] with arr[i + gap] and swap them if the first is bigger.
3. Shrink the gap: gap = ceil(gap / 2). After the pass with gap 1, stop.

class Solution {
    private int nextGap(int gap) {
        return gap <= 1 ? 0 : (gap + 1) / 2;    // half, rounded up
    }

    private void merge(int[] arr, int lo, int hi) {
        for (int gap = nextGap(hi - lo + 1); gap > 0; gap = nextGap(gap)) {
            for (int i = lo; i + gap <= hi; i++) {
                if (arr[i] > arr[i + gap]) {    // out of order across the gap
                    int t = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = t;
                }
            }
        }
    }

    public void mergeSort(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(arr, lo, mid);
        mergeSort(arr, mid + 1, hi);
        merge(arr, lo, hi);
    }
}

How long it takes: one merge of L numbers does about log L passes of L steps, O(L log L). Every level of the split tree adds up to n, so each level costs O(n log n) and there are log n levels: O(n log^2 n). Extra room: the waiting calls, O(log n). Swapping across gaps can reorder equal numbers, so this way is not stable.

Watch out for

• Rounding the gap down. For the stretch [4, 9, 1], 3 / 2 = 1 skips the gap 2 pass, and one pass with gap 1 leaves [4, 1, 9], still unsorted. Round up with (gap + 1) / 2, and stop after gap 1.
• In the sliding merge, forgetting mid++ after a slide. The left half grew by one, so the end of it moved.
• Using the gap merge when equal items must keep their order (for example, sorting records by one field). Use the sliding merge or a normal merge.
• "In place" here still uses O(log n) room for the recursion. A loop based (bottom up) merge sort removes even that.

What interviewers ask next

• Is there a true O(n log n) merge sort with O(1) extra room? Yes, block merge sorts like WikiSort and GrailSort, but they are long and tricky. In an interview, say they exist.
• If you only need O(n log n) time and O(1) room, what would you use? Heap sort. It is in place but not stable.
• Merge two sorted arrays without extra space, where the halves live in two different arrays? The same gap trick works across both arrays, treating them as one long array.
• Why do linked lists not have this problem? Merging lists only relinks nodes, so merge sort on a list needs no helper array at all.

Remember this

Grown-up words: splitting and merging is divide and conquer, sliding books over is shifting (like insertion sort), comparing across shrinking gaps is the Shell sort gap method, keeping equal items in order is stability, and the waiting calls are the recursion stack.