Merge a sorted array into a larger sorted array that has room to fit the smaller array.

So to start off, I made some assumptions about the end of the larger array: the space at the end is filled with -1 values. You could choose any value I guess, but that is the one that seemed a sensible value to me.

The naive solution to this problem is to simply create a new array the size of the large array and pick from one of two arrays as you iterate to fill the new array in sorted order. This would run in linear time, but it would use O(n) extra space (where n is the size of the larger array).

If space is a concern, the following solution runs in O(1) space:

This solution simply swaps out the max of either array with the next position in the buffer. The effect is that you get a sort of “sliding window” that shrinks as you swap out for items from the smaller array:

ar1 =  1 5 9 10 15 20 -1 -1 -1 -1
ar2 = 2 3 8 13
ar1 =  1 5 9 10 15 -1 -1 -1 -1 20
ar2 = 2 3 8 13
ar1 =  1 5 9 10 -1 -1 -1 -1 15 20
ar2 = 2 3 8 13
ar1 =  1 5 9 10 -1 -1 -1 13 15 20
ar2 = 2 3 8 -1
ar1 =  1 5 9 -1 -1 -1 10 13 15 20
ar2 = 2 3 8 -1
ar1 =  1 5 -1 -1 -1 9 10 13 15 20
ar2 = 2 3 8 -1
ar1 =  1 5 -1 -1 8 9 10 13 15 20
ar2 = 2 3 -1 -1
ar1 =  1 -1 -1 5 8 9 10 13 15 20
ar2 = 2 3 -1 -1
ar1 =  1 -1 3 5 8 9 10 13 15 20
ar2 = 2 -1 -1 -1
ar1 =  1 2 3 5 8 9 10 13 15 20
ar2 = -1 -1 -1 -1