Saturday, January 22, 2011

Merge two sorted arrays

Given two sorted arrays A and B with X and Y elements. The array A has X+Y space. Now merge array A and B in the array A with minimum number of steps and without using any auxiliary array space.

Approach:

Lets start with an example with array
A = {7, 9, 14, 19, _ , _, _, _, _}
B = {4, 12, 17, 18, 23}

So, the final configuration should be
A = {4, 7, 9, 12, 14, 17, 19, 23}

The simplest naive approach comes from the concept of the insertion sort, compare iteratively successive elements of array B to the elements in array A and if it is greater, then move all the elements in A by one position forward from that index and insert the element B in the current position. Code is left as an exercise to the reader.


Now most of us must have start thinking of the other sorting techniques to make this method faster.
Merge sort is the best suited one since it also merges the two sorted lists. But it requires an auxillary array to store the sorted list. Can we do without an auxillary array.
Yes, we can! An important observation is that the array A holds the extra space,
We can start from the right and start sorting with the highest element (in this way we no more are required to shift the elements, proof is again left to reader :))

So maintain 3 indexes,
first index of array A element (initialized to last element of A)
second index of array B element (initialized to last element of B)
third index in array A where the next highest element is to be stored

We will stop when all the elements of B are inserted in A (i.e when secondindex == -1)
 
B = {4, 12, 17, 18, 23}
All the operation will be on array A
Step 1 : A = {7, 9, 14, 19, _ , _, _, _, 23} (23 > 19)
Step 2 : A = {7, 9, 14, 19, _ , _, _, 19, 23} (19 > 18)
Step 3 : A = {7, 9, 14, 19, _ , _, 18, 19, 23} (19 > 18)
Step 4 : A = {7, 9, 14, 19, _ , 17, 18, 19, 23} (18 > 12)
Step 5 : A = {7, 9, 14, 19, 14, 17, 18, 19, 23} (17 > 12)
Step 6 : A = {7, 9, 14, 12, 14, 17, 18, 19, 23} (12 > 4)
Step 6 : A = {7, 9, 9, 12, 14, 17, 18, 19, 23} (9 > 4)
Step 6 : A = {7, 7, 9, 12, 14, 17, 18, 19, 23} (7 > 4)
Step 6 : A = {4, 7, 9, 12, 14, 17, 18, 19, 23}

Overall time complexity is O(X+Y),

9 comments :

  1. Sir
    we can find the position of every element of array B in array A in at most log n steps and creating space will require at most n steps//n is size of array A at any instance.so for each element of array B we require at most((log n) + n )steps..

    ReplyDelete
  2. @abhishek .. log(n) steps can be saved ...
    Regards

    ReplyDelete
  3. @aviral sir
    means we require just n steps ???

    ReplyDelete
  4. @abhishek... ohh i missed that u considered n is size of A ...it can be done in n=X+Y steps....

    ReplyDelete
  5. @aviral sir
    as there can be n comparisons (n is the sum of all elements in both the arrays )but movement of elements in order to create the space for element of array B would not require any extra step

    ReplyDelete
  6. @abhishek .. actually u never need to swap the elements if u start the comparison from the end of each array moving towards the first(just the slight variation of the merge function call in merge sort)...
    Regards

    ReplyDelete
  7. Abhishek PrajapatiJanuary 23, 2011 at 1:14 AM

    @aviral Sir
    I am not getting it sir as even if we start from the end we have to move the elements of array A to the right (just similar to insertion sort )and merge function puts the sorted arrays in a new array which is empty(so no doubt merging will require at most n steps)..
    sir plzz elaborate ,if I am wrong..

    ReplyDelete
  8. @abhishek .. starting from the last makes ur code efficient as it saves the swaps which u were doing (or may be creating the space) ...
    The example will elaborate a bit ...
    A = 2,7,8,_,_,_
    where _ represents the empty space
    B = 1,4,9
    Now the arrays merge will be
    All the operation will be on array A
    Step 1 : 2,7,8,_,_,9 (as 8<9)
    Step 2 : 2,7,8,_,8,9 (as 8>4)
    Step 3 : 2,7,8,7,8,9 (as 4<7)
    Step 4 : 2,7,4,7,8,9 (as 2<4)
    Step 5 : 2,2,4,7,8,9 (as 1<2)
    Step 6 : 1,2,4,7,8,9
    Overall there are n steps ... but u saved the time to swap the elements (as compared to when u start from the beginning of array)
    Regards

    ReplyDelete
  9. Abhishek PrajapatiJanuary 23, 2011 at 2:14 AM

    @aviral
    i got it, thanxs for this nice approach..when you told me to start from the end I thought starting from the position where the last element is present in array A,thats why I had confusion of creating the space but now its clear....thnxs again

    ReplyDelete