Write a function that merges two sorted integer arrays using no other buffer than the one you are given.

One of the arrays consists of data and an empty space called buffer. This array is the primary array because this is where you will store the result of the merge. Even though the buffer contains integers, we consider it empty. Consider the following example primary array P.

Primary Array

The other array is at most the size of the buffer and consists of data. This array is the secondary array because it contains the elements that you will merge into the primary array. Consider the following example secondary array S that corresponds to the example primary array.

Secondary Array

The expected final state of P given S is the following.

Expected Primary

The integer of position 9 in the final state is unspecified because we do not care about what’s beyond the length of the result of the merge.

Input. The input to your function consists of a reference to the principal array, a reference to the secondary array, and the length of the data. For example, for the example primary and secondary arrays, the length of the data is 6.

Output. The output of your function consists of the expected final state of the primary array and the length of the merge. Given that the final state of the primary array is available through any reference to the array, the only return value of your function is the length of the merge. For example, for the example primary and secondary arrays, the length of the merge is 9.

Solution

We merge data and the secondary array by copying their elements from right to left in descending order. We write the elements in the primary array from right to left starting from the last position.

To illustrate the procedure, consider the following diagram of the example primary and secondary arrays.

Positions of last elements and tail of buffer

Position i corresponds to the last element of the data. Position j corresponds to the last element of the secondary array S. Position t is the last position in the primary array P.

Given positions i, j, and t, we write the last four elements of the result as illustrated by the following diagram. The order we follow is green, yellow, red, and purple.

Writing of the last four elements of the result

For the rest of the result, we continue with the merge of data and the secondary array in descending order. In doing so, we overwrite positions 1 to 5 of the primary array P.

Writing of the rest of the elements of the result

After the merge, we shift the result to the right and thus obtain the following final state of P.

The final state of the primary array

Implementation

We implement the solution in Ruby as follows.

def merge_by_buffer p, s, l
  i = l - 1
  j = s.length - 1
  t = p.length - 1
  while i >= 0 or j >= 0
    if i >= 0 and j >= 0
      if p[i] > s[j]
        p[t] = p[i]
        i -= 1
      else
        p[t] = s[j]
        j -= 1
      end
    elsif i >= 0
      p[t] = p[i]
      i -= 1
    else
      p[t] = s[j]
      j -= 1
    end
    t -= 1
  end
  t += 1
  h = 0
  while t < p.length
    p[h] = p[t]
    h += 1
    t += 1
  end
  return h
end

Want to read more?

I regularly write solutions to programming problems that you may or may not find in technical job interviews. I also love to explain those solutions and answer questions. If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments