# Merge by Buffer

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`

.

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.

The expected final state of `P`

given `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.

# 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.

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.

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`

.

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

.

# Implementation

We implement the solution in Ruby as follows.

# Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to 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.