Merge 2 sorted arrays without using Extra space

The problem, simply

You get two sorted arrays, arr1 with m numbers and arr2 with n numbers. Rearrange the numbers so that if you read arr1 and then arr2, everything is in sorted order. So arr1 ends up with the m smallest numbers and arr2 with the rest, both sorted.

The catch: you may not use another array. Only a few extra variables.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use a spare row after all. Merge both into a new array with two fingers, then copy the first m numbers back into arr1 and the rest into arr2. This breaks the rule, but it is the baseline and it shows what the answer must look like.

class Solution {
    public void merge(int[] arr1, int[] arr2) {
        int m = arr1.length, n = arr2.length;
        int[] temp = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) temp[k++] = (arr1[i] <= arr2[j]) ? arr1[i++] : arr2[j++];
        while (i < m) temp[k++] = arr1[i++];
        while (j < n) temp[k++] = arr2[j++];
        for (i = 0; i < m; i++) arr1[i] = temp[i];       // small ones back to arr1
        for (j = 0; j < n; j++) arr2[j] = temp[m + j];   // big ones to arr2
    }
}

How long it takes: each number is copied twice, O(m + n). Extra room: the spare row, O(m + n).

Way 2: the clever way

Pretend the two rows are one long row of len = m + n spots. Position k means arr1[k] when k < m, and arr2[k - m] otherwise.

1. Start with gap = ceil(len / 2).
2. Put finger i at 0 and finger j at gap. While j is inside the long row: if the number at i is bigger than the number at j, swap them. Move both fingers one step.
3. If gap was 1, stop. Otherwise gap = ceil(gap / 2) and go back to step 2.

Big gaps fix numbers that are far from home in one jump. The last pass, with gap 1, is like one pass of bubble sort, and by then only a few neighbours are out of order.

class Solution {
    public void merge(int[] arr1, int[] arr2) {
        int len = arr1.length + arr2.length;
        int gap = (len + 1) / 2;                       // ceil(len / 2)
        while (gap > 0) {
            for (int i = 0, j = gap; j < len; i++, j++) {
                if (get(arr1, arr2, i) > get(arr1, arr2, j)) swap(arr1, arr2, i, j);
            }
            if (gap == 1) break;                       // the neighbour pass is the last one
            gap = (gap + 1) / 2;                       // ceil(gap / 2)
        }
    }

    // Spot k of the long row: arr1 first, then arr2.
    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;
    }

    private void swap(int[] a, int[] b, int i, int j) {
        int t = get(a, b, i);
        put(a, b, i, get(a, b, j));
        put(a, b, j, t);
    }
}

How long it takes: the gap halves each round, so there are about log(m + n) rounds, and each round walks the long row once: O((m + n) log(m + n)). Extra room: a few variables, O(1).

Another way: swap the ends, then sort each row

There is an even simpler idea with the same cost. The biggest numbers of arr1 and the smallest numbers of arr2 are the ones in the wrong row.

1. Put i at the last spot of arr1 and j at the first spot of arr2.
2. While arr1[i] > arr2[j], swap them, then move i left and j right.
3. Now every number is in the right row, but each row may be out of order. Sort both rows.

On the example: 10 swaps with 2, 8 swaps with 3, then 7 is not bigger than 9, so stop. The rows are [1, 4, 7, 3, 2] and [10, 8, 9]. Sorting them gives the answer.

class Solution {
    public void merge(int[] arr1, int[] arr2) {
        int i = arr1.length - 1, j = 0;
        while (i >= 0 && j < arr2.length && arr1[i] > arr2[j]) {
            int t = arr1[i]; arr1[i] = arr2[j]; arr2[j] = t;   // send each to the right row
            i--;
            j++;
        }
        Arrays.sort(arr1);
        Arrays.sort(arr2);
    }
}

This is O((m + n) log(m + n)) time because of the sorting, and no extra array. Interviewers who ask for the gap method usually also accept this one if you explain why the swaps put every number in the right row.

Watch out for

• Stop after the gap 1 pass. Without if (gap == 1) break, ceil(1 / 2) is 1 again and the loop never ends.
• Mapping the long row index to the two arrays is easy to get wrong. Keep it in one small helper like get.
• A common wrong shortcut walks arr1 from the end, swaps with arr2[0] and re-sorts only arr2. That leaves arr1 out of order. Walking arr1 from the front with that same swap is the correct, but slow, O(m n) version.

What interviewers ask next

• What if arr1 has n empty slots at the end (LeetCode 88)? Then fill from the back: compare the last real numbers of both and write the bigger one at the very end. That is O(m + n) with no extra room.
• Why is the gap method correct? The final gap 1 pass alone does not sort everything, but the bigger gaps have already moved every number close to home, the same idea as shell sort.
• Can you do it in O(m + n) time and O(1) room for this exact version? There are complex in-place merge algorithms, but they are not expected in interviews.
• How would you merge k sorted arrays? Use a min heap holding the front of each array.

Remember this

Grown-up words: no spare row means in place with O(1) extra space, comparing across a gap is the shell sort idea, and the final gap 1 pass is one round of bubble sort.