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
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
The expected final state of
S is the following.
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.
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.
i corresponds to the last element of the data. Position
j corresponds to the last element of the secondary array
t is the last position in the primary array
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.
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
After the merge, we shift the result to the right and thus obtain the
following final state of
We implement the solution in Ruby as follows.
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.