Jun 282012
 

There are 2 sorted arrays of size m and m+n respectively. First array (of size m) has m elements and Second array (of size m+n) has only n elements (last m positions are blank). So, the total number of elements in both the arrays is m+n (m in first and n in second). Write code to merge the m+n elements in the 2nd array such that the result is sorted.

If the two arrays are as below:

Then the output should be:

Solution:

Start the backward merge, of array arr1 and n elements on arr2 into arr2 (Complete array, till position m+n) 

Algorithm:

1. Let a, b & c be three pointers.

  • a points to last (mth) element of arr1
  • b points to nth (last valid) element of arr2
  • c points to the last empty position of arr2 (m+n)th

2. While ( a>=0 && b>=0). i.e will we have elements in both the arrays

    If (arr1[a] > arr2[b])
        arr2[c] = arr1[a]
            a--
    else
        arr2[c] = arr2[b]
        b--
    c--

3. If a >=0
Move remaining elements from arr1 to arr2 starting from a in arr1 to position c in arr2 in backward fashion

Code:

    /** size of array arr2 should be m+n (and not n) */
    void mergeIntoSecond(int * arr1, int m, int*arr2, int n)
    {
        int a=m-1, b=n-1, c=m+n-1;
        while(a>=0 && b>=0)
        {
            if(arr1[a] > arr2[b])
            {
                arr2[c] = arr1[a]; 
                a--;
            }
            else
            {
                arr2[c] = arr2[b]; 
                b--;
            }
            c--;
        }

        for(;a>=0;a--, c--)
            arr2[c] = arr1[a];
    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)