Merge 2 sorted arrays

The problem, simply

You get two sorted arrays, a with n numbers and b with m numbers. Rearrange the numbers so that if you read a and then b, everything is in sorted order. So a must end up holding the n smallest numbers, sorted, and b the rest, sorted.

The catch: you may not use a third array. Only a few extra variables. You must move numbers around inside a and b themselves.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use a big spare table after all. Merge both shelves into a new array with two fingers, one on each shelf. Each time, take the smaller book under the two fingers. Then copy the first n books back into a and the rest into b.

1. Put finger i on a[0] and finger j on b[0].
2. Copy the smaller of a[i] and b[j] into the new array and move that finger.
3. When one shelf runs out, copy the rest of the other shelf.
4. Copy the new array back into a and b.

class Solution {
    public void merge(int[] a, int[] b) {
        int n = a.length, m = b.length;
        int[] all = new int[n + m];
        int i = 0, j = 0, k = 0;
        while (i < n && j < m) {
            if (a[i] <= b[j]) all[k++] = a[i++];   // take the smaller book
            else all[k++] = b[j++];
        }
        while (i < n) all[k++] = a[i++];          // leftovers from a
        while (j < m) all[k++] = b[j++];          // leftovers from b
        for (k = 0; k < n; k++) a[k] = all[k];    // first n go back to a
        for (k = 0; k < m; k++) b[k] = all[n + k];
    }
}

How long it takes: every number is copied twice, O(n + m). Extra room: the spare array, O(n + m). This is the fastest way, but it breaks the "no third array" rule.

Way 2: the clever way

Treat a and b as one long row of n + m boxes: positions 0 to n - 1 are in a, and positions n onward are in b. Then compare boxes that are a "gap" apart and swap them when the left one is bigger.

1. Start with gap = ceil((n + m) / 2).
2. Slide two fingers gap apart from the left end to the right end. At each stop, if the left box is bigger than the right box, swap them.
3. If gap was 1, stop. Otherwise set gap = ceil(gap / 2) and repeat.

Big gaps carry a far out of place number most of the way in one swap. The final gap of 1 is a neighbor check that cleans up the rest. This idea comes from shell sort.

class Solution {
    public void merge(int[] a, int[] b) {
        int n = a.length, m = b.length, total = n + m;
        int gap = (total + 1) / 2;                 // ceil(total / 2)
        while (true) {
            for (int i = 0; i + gap < total; i++) {
                int j = i + gap;
                if (get(a, b, i) > get(a, b, j)) { // left box is bigger: swap
                    int t = get(a, b, i);
                    put(a, b, i, get(a, b, j));
                    put(a, b, j, t);
                }
            }
            if (gap == 1) break;
            gap = (gap + 1) / 2;                   // ceil(gap / 2)
        }
    }

    // position k lives in a when k < n, otherwise in b
    private int get(int[] a, int[] b, int k) {
        return k < a.length ? a[k] : b[k - a.length];
    }

    private void put(int[] a, int[] b, int k, int v) {
        if (k < a.length) a[k] = v; else b[k - a.length] = v;
    }
}

How long it takes: there are about log(n + m) gap sizes, and each one walks the whole row, O((n + m) log(n + m)). Extra room: a few variables, O(1).

Another way: swap the ends, then sort

There is a shorter trick that also uses no third array. The biggest numbers of a sit at its right end and the smallest numbers of b sit at its left end. Walk inward from both of those ends at once: while a[i] > b[j], swap them. When the swap stops, every number in a is small enough. Each shelf is now jumbled a little, so sort each one.

class Solution {
    public void merge(int[] a, int[] b) {
        int i = a.length - 1, j = 0;
        while (i >= 0 && j < b.length && a[i] > b[j]) {
            int t = a[i]; a[i] = b[j]; b[j] = t;   // big from a goes to b
            i--;
            j++;
        }
        Arrays.sort(a);
        Arrays.sort(b);
    }
}

This is O(n log n + m log m) time. It is easy to explain, but Arrays.sort on int[] uses some stack room inside, so the gap method is the pure O(1) answer.

Watch out for

• Mixing up which array a position belongs to. Position k is a[k] when k < n, else b[k - n].
• Forgetting the stop after the gap 1 pass. ceil(1 / 2) is 1 again, so without the break the loop never ends.
• Using >= in the swap test. That swaps equal numbers for nothing. Use >.
• One of the arrays is empty. All the loops still work, but test it.

What interviewers ask next

• The LeetCode version: a has n + m slots and only the first n are filled. Fill from the back: put the bigger of a[i] and b[j] into the last free slot. Working from the back never overwrites a number you still need. That is O(n + m) time and O(1) room.
• Merge k sorted arrays. Put the first number of each array into a min heap, pop the smallest, and push the next number from the same array. That is O(N log k).
• Why is merging the heart of merge sort? Merge sort splits the array until pieces have one number, then merges sorted pieces with exactly the two finger loop from Way 1.
• Is the gap method stable, meaning do equal numbers keep their order? No. Swaps across a gap can jump one equal number over another.

Remember this

Grown-up words: the two shelves are two sorted arrays, the fingers are two pointers, the shrinking gap is the gap method from shell sort, and "no third array" means O(1) auxiliary space, an in-place merge.