Merge 2 Sorted Arrays (one has empty slots)

Question: There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

Solution: The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.



Code (C#):
// A1 and A2 are two sorted arrays. 
// A2 is not completely full (has empty slots at the end and are exactly the 
// size of A1)
// the goal is to merge the two arrays in a sorted fashion

void Merge(int[] A1, int[] A2)
{
   int count = FindCount(A2); // get the count of full slots
   int i = A1.Length - 1;
   int j = count - 1;
   int k = A2.Length - 1;

   for(;k>=0;k--)
   {
      if(A1[i] > A2[j] || j < 0)
      {
         A2[k] =A1[i];
         i--;
      }
      else
      {
         A2[k] = A2[j];
         j--;
      }
   }
}

7 comments:

  1. i think there is a mistake in the index for smaller, it should be j instead of i.

    ReplyDelete
  2. thanks for the feedback. I revised the problem description and the solution.

    ReplyDelete
  3. Have you tried running this code ? I think it will give ArrayIndexOutofBounds (or similar exception) on line:
    if(A1[i] > A2[j] || j < 0)

    ReplyDelete
  4. void merge(int[] A1, int[] A2)
    {
    int count = findCount(A2); // get the count of full slots
    int i = A1.length - 1;
    int j = count - 1;
    int k = A2.length - 1;

    for(;k>=0;k--)
    {
    if((i >= 0 && j >= 0 && A1[i] > A2[j]) || j < 0)
    {
    A2[k] =A1[i];
    i--;
    }
    else if((i >= 0 && j >= 0 && A1[i] <= A2[j]) || i < 0)
    {
    A2[k] = A2[j];
    j--;
    }
    }
    }

    ReplyDelete
  5. void Merge(int[] A1, int[] A2)
    {
    int count = FindCount(A2); // get the count of full slots
    int i = A1.Length - 1;
    int j = count - 1;
    int k = A2.Length - 1;

    for(;k>=0;k--)
    {
    if(A1[i] > A2[j] || j < 0)
    {
    A2[k] =A1[i];
    i--;
    if(i<0)
    break;
    }
    else
    {
    A2[k] = A2[j];
    j--;
    }
    }
    }

    ReplyDelete
  6. // Both the above code doesn't work and produces invalid result. Here is the correct code and works perfectly for the above example.

    void mergeArray(int[] A1, int[] A2)
    {
    int count = FindCount(A2); // get the count of full slots
    int i = A1.Length - 1;
    int j = count - 1;
    int k = A2.Length - 1;

    for (; k >= 0; k--)
    {
    if ((i >= 0 && j >= 0 && A1[i] > A2[j]) || j < 0)
    {
    A2[k] = A1[i--];
    }
    else if ((i >= 0 && j >= 0 && A1[i] <= A2[j]))
    {
    A2[k] = A2[j];
    A2[j--] = A1[i];
    }
    }

    for (int l = 0; l < A2.Length; l++)
    Console.WriteLine(A2[l]);
    }

    ReplyDelete
  7. public int[] merge(int[] l, int[] r){
    int li = 0, ri = 0, index = 0;
    int[] result = new int[l.length + r.length];
    while(index < (l.length + r.length)){
    if(ri >= r.length || ((li < l.length) && (l[li] <= r[ri]))){
    result[index] = l[li];
    li++;
    }else{
    result[index] = r[ri];
    ri++;
    }
    index++;
    }
    return result;
    }

    ReplyDelete