Merge two sorted arrays in place in O(1) space

Question

Can someone please help me understand the algorithm / code for this problem

given two integer arrays, sort them such that, initial numbers are placed in first array and remaining numbers in second array. For example:

Input: ar1[ ] = {1, 5, 9, 10, 15, 20}

        ar2[] = {2, 3, 8, 13}

Output: ar1[ ] = {1, 2, 3, 5, 8, 9}

         ar2[] = {10, 13, 15, 20} 

Code:

    void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
    {
        //Find the smallest element greater than ar2[i]. Move all
        //   elements one position ahead till the smallest greater
        //   element is not found
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
        {
            ar1[j+1] = ar2[i];
            ar2[i] = last;
        }
    }
}

I saw this solution on this website : http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Answer 1

Intuition

For each element ar2[i] of ar2(i.e. inside the outer loop) basically you find the index j in ar1 such that all the elements of ar1 in range [(j+1), (m-1)] are greater than ar2[i]. Then you take the smallest element in that range and throw it off of ar1 to ar2, specifically to the cell with index i, where the value in ar2[i] once resided before being transferred to ar1.

The reason of this transfer of ar2[i] to ar1[j+1] is the effort to gather the smallest m elements in ar1 and the rest in ar2. The arguably elegant thing this algorithm does is traversing ar2 from right to left. If you recall that both ar1 and ar2 are sorted, what going from right to left on ar2 helps achieve using constant extra space is as follows.

As you go from right to left on ar2 you encounter decreasing, or at least non-increasing, values in ar2[i]. This means that you will find decreasing or non-increasing values of ar1[m-1] to replace them with. Basically the smallest elements ar1[m-1] greater than ar2[i] will be non-increasing as the value ar2[i] decreases as we go from right to left.

Consequently, the elements we throw off ar1 to arr2 in each iteration of outer loop will also be in non-increasing or decreasing order, and we will place them to indices in decreasing order, keeping ar2 ordered.

Invariant Approach

A possible though rather informal invariant would be that ar1 and ar2 would be sorted after each iteration, with at most a single element of ar2, say ar2[i], for which there exist at least 1 ar1[k]>ar2[i] is swapped with an element in ar1 in a manner not violating the sorted order of either array.

Initially the elements are ordered. After each iteration, if there exists an element smaller than ar2[i] in ar1 at index j, all range greater than ar2[i] is shifted to right by 1. ar2[i] is placed to ar1[j+1] so that it does not violate the order of ar1. Then, the previously last element of ar1, which does not fit in ar1 anymore, is put ito ar2[i].

It is straightforward to see that order of ar1 is maintained at each iteration of the outer loop. Order of ar2 requires a bit more of focus.

Every time we put an element of ar2 to ar1, we know that the previously last element of ar1 we will put to ar2 (i.e. in place of ar2[i]) is known to be greater than ar2[i], as it is greater than or equal to ar1[j+1] which was greater than ar2[i]. (ar2[i] < ar1[j+1] <= last)

Also, any previously replaced elements in ar2(i.e. the ones to the right of the ith index of ar2) have been replaced with values last that were greater than or equal to the value last in current iteration, as ar1 was initially ordered.

Therefore after each iteration, ar2 remains ordered as well, and after the algorithm terminates, there exists no element ar2[i] such that there is an element ar1[k] > ar2[i].