# Given two sorted arrays, add the elements of the second array into the first

In Cracking the Coding Interview by Gayle Laakmann McDowell, there's a question that asks you to write code for the following:

Given two sorted arrays, A and B. Write a method merging the elements of B into A in sorted order. Assume A has a large enough buffer at the end to hold all of B's elements.

Though the problem isn't very hard, I've been striving to increase the readability of my code in general. As such, I wrote two versions of my solution, and am looking for input on which version is most readable.

Version 1:

// Given two sorted arrays, adds the elements of the second array into
// the first, while maintaining ordering property.
// XXX: Assumes first array has enough buffer space to hold all elements
public static <Type extends Comparable<Type>> Type[]
mergeIntoFirstArray(Type[] first_array, Type[] second_array) {

int first_idx         = numElementsInArray(first_array) - 1;
int second_idx        = second_array.length - 1;
int merge_idx        = numElementsInArray(first_array) + second_array.length - 1;    //

// merge largest values first, until either array is exhausted
while (first_idx >= 0 && second_idx >= 0) {
Type first_value    =  first_array[first_idx];
Type second_value    =  second_array[second_idx];

if (first_value.compareTo(second_value) > 0){
first_array[merge_idx] = first_value ;
first_idx--;
} else {
first_array[merge_idx] = second_value ;
second_idx--;
}
merge_idx-- ;
}

// if second_array still has values, merge them in
while (second_idx >=0) {
first_array[merge_idx] = second_array[second_idx] ;
merge_idx-- ;
second_idx--;
}

return first_array ;
}


Version 2:

public static <Type extends Comparable<Type>> Type[]
mergeIntoFirstArrayV2(Type[] first_array, Type[] second_array) {
int f    = numElementsInArray(first_array)-1;
int s    = second_array.length - 1;

// merge in largest values first
for (int merge_idx = f + s + 1 ; merge_idx >= 0 ; merge_idx--) {
Type fvalue    =  f >= 0 ? first_array[f]  : null;
Type svalue    =  s >= 0 ? second_array[s] : null;

// first value exists, and is greater than second value
if (fvalue != null &&
(svalue == null || fvalue.compareTo(svalue) > 0)) {
first_array[merge_idx] = svalue ;
s_idx--;
}
else {
first_array[merge_idx] = svalue ;
s_idx--;
}
}

return first_array ;
}


Any meaningful input on improving the readability of either method would also be appreciated. For one, I think my variable names might be unclear or too long in some cases. For version 2, I suspect that though the code is more concise, it is harder to understand at a glance.

-
In-place modification is silly though. A whole new array / list should be created instead. If only Java had a yield keyword ... –  Leonid Nov 21 '12 at 23:12
I thought it was a pain too, and only reused the parameter array because of the problem description. I'm not sure how yield would help in this scenario, though. Knowing a little bit about python, having a 'yield' feature would allow you to make a generator function that could return the merged values (one value returned after each function call?). If you don't mind explaining, how would this be advantageous for this particular problem? –  hagaren Nov 23 '12 at 1:07
I am all about splitting a problem into as small chunks as possible. Sometimes it is more convenient to yield in one function and collect that into a real data structure later than to mix the generation and the collection of the output in one. Obviously, it is not a major factor. However, if Java had a yield as well as a look-ahead iterator (something that allows to peek cheaply), then this problem would have a beautiful solution. Otherwise, it feels kind of ugly at the end. –  Leonid Nov 23 '12 at 13:45
I am not sure, but I do not think that you can find a good implementation for numElementsInArray if you use generics. Because there is no good way to know an "empty" element. –  tb- Nov 23 '12 at 19:26

Both are equivalently readable, I'll nitpick on some details though :)

Both solutions will fail with null elements.

The generic type would be better named T instead of Type, as Type has another definition already.

numElementsInArray() as a function looks a little odd because it is undefined, instead consider passing in the information you need as part of the method definition.

When modifying in place you do not want to return the array because presumably you are trying to skimp on memory allocations and are just going to look for the result in the first array that was passed in.

-
As soon as you said it, I realized I hadn't taken null values into account. Actually, I frequently forget to check or validate input. And I hadn't noticed Type had another definition, either. The last two suggestions are something I couldn't decide either way when coding: I have both versions of mergeIntoFirstArray() returning Type[] to save myself a line of code when testing the methods. I used numElementsInArray() because I wasn't certain whether I should have the user enter the number of elements in the first array. Anyway, thanks, I appreciate your assessment. :) –  hagaren Nov 23 '12 at 1:02

Given two sorted arrays, A and B. Write a method merging the elements of B into A in sorted order. Assume A has a large enough buffer at the end to hold all of B's elements.

This is my approach:

public static <T extends Comparable<T>> void mergeSecondArrayInFirstArrayOrdered(final T[] array1, final T[] array2) {
// we could (should!) add checks for the given contract. Do not trust the world
for (int i = 1; i <= array2.length; ++i)
array1[array1.length - i] = array2[array2.length - i];
Arrays.sort(array1);
}
// edit: got a hint for a small change. One could discuss which version should be used
// System.arraycopy uses a native implementation, which should be faster, but you lose
public static <T extends Comparable<T>> void mergeSecondArrayInFirstArrayOrdered2(final T[] array1, final T[] array2) {
System.arraycopy(array2, 0, array1, array1.length - array2.length, array2.length);
Arrays.sort(array1);
}


Ok, you can say now this is not expected. But, well, it confirms to the question and it is a good solution because you use a well known, good tested and designed Java method. So for your employer the benefits are reduced time instead of doing this rather long merge by hand, and reduced support costs because this code is very easy to check and understand. If your employer is clever, he will get the point.
Keep in mind, that this works only for Object arrays. For arrays of primitive array types, you have to implement it for all 8 types.

(One could have an argument about speed because of the sort. I advice you to not trust this argument before profiling.)

-

Clearly the crux of the question was that you have to fill the array from the end, and you got that right.

In the second version, the fact that all elements of an array has been handled is represented in the program state by assigning null to the value variables. And when reading the following if statement you have to go back to lines where the values are assigned to see how they can be null. You should just check if firstIdx < 0 in simpler cases like this or use a private method or local variable with a meaningful name if it is not clear what the boolean expression means. In that way first version is clearly superior. (It also doesn't have the ternary operator ?:, which always helps.)

firstArrayFinished = firstIdx < 0;
// ..................
// ..................
// ..................
// ..................
if (firstArrayFinished || s.compareTo(f) > 0) {
// ..................
}


I agree totally with Timothy Pratley, on his remarks. Even if there is no question of confusion with another identifier, you should still use single capital letters or similar short identifiers as type variables, so that it is instantly clear for the reader of the code that it is not an actual class or interface. When you browse code in an IDE or grep some source folder you never see the imports section and it becomes an effort to check the method signature every time just to be sure becomes a burden. (Also lose the underscores, if you are a java programmer.)

Although the standard library has similar methods, a method doing anything in place means its modifying something and should return void. The library methods that do both in place modification and return arrays do that because they do array allocation if some parameters are null. I do not know if return type was in the problem specification.

numElementsInArray(first_array) is also problematic. If an array is passed as a parameter and it's empty after some index, you pass another parameter int len to indicate the number of elements.

-

Edit: OK, fine, in Java:

// Precondition: dest[0..n-1] and source[] are both sorted increasing.
// Postcondition: dest[0..n+source.length-1] is the sorted merge of
//   the original dest[0..n-1] and source[], and source[] is unchanged.
public static <Type extends Comparable<Type>>
void mergeInto(Type[] dest, int n, Type[] source) {
int s = source.length;      // reading from source
int d = n;                  // reading from dest
int w = n + s;              // writing to dest
while (0 < s) {
while (0 < d && source[s-1].compareTo(dest[d-1]) < 0) {
dest[--w] = dest[--d];
}
dest[--w] = source[--s];
}
}


Untested. (edit: tested by @climmunk, yay!) That was why my original answer, below, was in Python, so I wouldn't be foisting untested code on you. Note that this code provides a slightly different interface than the questioner's, which is intentional: it's part of the code review.

Original answer: Here's the algorithm I'd use (coded in Python since I don't know C#):

def merge_into(A, n, B):
"""Pre: A[:n] and B are both sorted.
Post: B is unaltered, and A_post[:n+len(B)] == sorted(A_pre[:n]+B)"""
j, k = n, n + len(B)
for b in reversed(B):
while 0 < j and b < A[j-1]:
j -= 1
k -= 1
A[k] = A[j]
k -= 1
A[k] = b


Trying it out:

>>> A = [3, 4, 5, 9, None, None, None]
>>> B = [1, 1, 4]
>>> merge_into(A, 4, B)
>>> A
[1, 1, 3, 4, 4, 5, 9]

-
Do you know Java? :) –  dreza Nov 23 '12 at 3:36
Not since before generics were added. Sorry for the trivial confusion. The point, though, is the simpler algorithm: just a loop within a loop, with no ifs. –  Darius Bacon Nov 26 '12 at 20:13
This is a nice algorithm, cleaner than OP's. I tested the Java code, and it works. Not sure why it's getting downvoted. –  climmunk May 23 at 17:33
You have a case of the Yoda conditions :P –  BeetDemGuise May 23 at 18:06
I consistently use < instead of >, most of the time, because you can visualize a<b: a is to the left of b on the number line. Then more complex conditions like a <= b && b < c become easier to think about. –  Darius Bacon May 23 at 22:59