How merge sorted arrays into one

Question: given 2 sorted arrays. First array has X elements and of size X. Second array has Y elements and size N where N = X + Y. Merge the first array to the second array and return the second array so that the new second array is also sorted.

I encountered this question in an interview with a big software company in Seattle. So, I thought it would be useful to share it.

Let's look at an example to understand the problem better. If we have two arrays: array1 = {1, 3, 5, 9} and array2 = {2, 6, 8, 10}, the merged array is array2 = {1, 2, 3, 5, 6, 8, 9, 10}. Note that according to the question, array2 has enough free space to contain all elements of array1.

Here is how we're gonna solve this. Assume that we have two int arrays for simplicity, the code looks like this:

int* mergeSortedArray(int array1[], int numOf1Elements, int array2[], int numOf2Elements)
{
  int pivotIndex = numOf1Elements + numOf2Elements - 1;
  
  int array1Index = numOf1Elements - 1;
  int array2Index = numOf2Elements - 1;

  while (array1Index >= 0 && array2Index >= 0)
  {
    if (array1[array1Index] >= array2[array2Index])
    {
      array2[pivotIndex] = array1[array1Index];
      array1Index--;
    }
    else
    {
      array2[pivotIndex] = array2[array2Index];
      array2Index--;
    }
    pivotIndex--;
  }

  if (array1Index >= 0)
  {
    while (array1Index >= 0)
    {
      array2[pivotIndex] = array1[array1Index];
      pivotIndex--;
      array1Index--;
    }
  }

  return array2;
}

First, get the index of the last cell in array2, called pivotIndex. Next, we get the index of the last element in array1, named array1Index, and the index of the last element in array2, named array2Index.

Secondly, we loop through the arrays until either array1Index and array2Index becomes negative. For each iteration, we look at the values at array1[array1Index] and at array2[array2Index]. If array[array1Index] is greater than or equal to array2[array2Index], we put it at the end of array2, ie. array2[pivotIndex]. Otherwise, we put array2[array2Index] at array2[pivotIndex]. This gives the effect that all big values are pushed at the end of the array in order. Also, if an element from array1 gets put in array2, we decrement the array1Index by one to access to the next element in array1. Otherwise, we decrement array2Index by one to access to the next element in array2. After all that, we need to decrement pivotIndex by one to move to the next available cell in array2.

Lastly, we just copy leftover elements in array1 into array2. How do we know if array1 has leftover after the main loop? Well, if array1Index is still >= 0 then there is leftover in array1

If you are confused, use a piece paper and pencil to trace the code using the arrays in the example. It will clear things up. I promise :)