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

Question

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];

        // add the largest value
        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.

Answer 1

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.

Answer 2

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
// readability (and type safety)
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.)

Answer 3

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.

Answer 4

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]