How to merge two sorted arrays into a sorted array?

Question

This was asked of me in an interview and this is the solution I provided:

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;
}

Is there a more efficient way to do this?

Edit: Corrected length methods.

Solution 1

A minor improvement, but after the main loop, you could use System.arraycopy to copy the tail of either input array when you get to the end of the other. That won't change the O(n) performance characteristics of your solution, though.

Solution 2

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)  
       answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

    while (i < a.length)  
        answer[k++] = a[i++];

    while (j < b.length)    
        answer[k++] = b[j++];

    return answer;
}

Is a little bit more compact but exactly the same!

Solution 3

I'm surprised no one has mentioned this much more cool, efficient and compact implementation:

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;
}

Points of Interests

1. Notice that it does same or less number of operations as any other O(n) algorithm but in literally single statement in a single while loop!
2. If two arrays are of approximately same size then constant for O(n) is same. However if arrays are really imbalanced then versions with System.arraycopy would win because internally it can do this with single x86 assembly instruction.
3. Notice a[i] >= b[j] instead of a[i] > b[j]. This guarantees "stability" that is defined as when elements of a and b are equal, we want elements from a before b.

Solution 4

Any improvements that could be made would be micro-optimizations, the overall algorithm is correct.

Solution 5

This solution also very similar to other posts except that it uses System.arrayCopy to copy the remaining array elements.

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length +b.length];
    int i =0; int j = 0;int k = 0;
    while(i<a.length && j <b.length) {
        if(a[i]<b[j]) {
            result[k++] = a[i];
            i++;
        } else {
            result[k++] = b[j];
            j++;
        }
    }
    System.arraycopy(a, i, result, k, (a.length -i));
    System.arraycopy(b, j, result, k, (b.length -j));
    return result;
}

View more solutions

Comments

[Drew Hall]

Looks like a pretty good answer to me. This problem will have O(n) complexity at best, and your answer achieves that. Anything else will be microoptimization.

[Matt Mitchell]

Reminds me how lazy LINQ makes you (return a.Union(b).OrderBy(i => i);) Perhaps with a .ToArray() at the end.

[Vladimir Dyuzhev]

You did good! This is essentially a part of merge sort: merging two sorted streams (from tape or disk) into another sorted stream.

[Shai]

Have you got the job?

[Anton Dozortsev]

Also you can use ternary operator: while (i < a.length && j < b.length) answer[k++] = a[i] < b[j] ? a[i++] : b[j++]; Java Language Specification: Conditional Operator ? :.

[Bravo]

for the input int[] a = {-1,6}; int[] b = {-11,-12}; output array is coming like below {-11,-12,-1,0}

[amitguptageek]

@Bravo I checked the above code with int[] a = {-1,6}; int[] b = {-11,-12}; and it is working fine.

[LiziPizi]

You forgot to comment!!!

[Kevin M]

Did they stipulate that there would not be any duplicates in the lists? Or that you shouldn't care about them? That's one issue I see with this code is that if the item in the first list is not less than the one in the second list, then you just take the one from the second list. So you will end up with pulling in duplicates, which may be fine for this exercise.

[ChuckZHB]

Thanks, clean code and clear logic!

[jack]

If a is large and b is small then this algorithm is wrong.

[jack]

It is not wrong but not efficient.

[Mike Saull]

To the person who said this caused an index out of bounds exception what inputs are you using? It works in all cases for me.

[Ahmadov]

I do not understand why this answer got negative votes. It is true that it is not efficient. But sometimes all you need is to get the job done as soon as possible. If you are dealing with very small arrays, say less than 100 elements, I would prefer to use the above code rather than writing a lengthy code that won't make any important performance improvements. So, thanks Sudhir for providing this easy solution and SANN3 for editing it.

[Will]

@jack how can you do it faster than O(n) when you are producing an array of n items?

[gsamaras]

Some explanation would be nice. :)

[gknicker]

This answer does not apply to the Java programming language, though it would be a good answer for javascript.

[Aki Suihkonen]

The unwritten premise is that a sort function can't use itself as a method of sorting. That would be infinite regression instead of recursion. Also the other premise is that merge_array is the function that implements sort. Thus this answer is unusable in the most likely context.

[Shital Shah]

The question asked didn't mention that required code was for only small array. So this answer would be misleading unless it clearly stated its limitation. Also look at my answer below. It takes same number of lines to write efficient code that works for any array size :)

[Chackle]

This is a really really nice approach. I had trouble getting good benchmarks on my Merge sort algorithms in Swift lang. Converting this gave me what I needed, thanks very much

[Hengameh]

+1, Thanks for sharing. One question: why did you select the type of array and type of variable 'temp', long?

[Hengameh]

What is the point of (j < 0) in the while loop? Btw, +1, This is really cool! Thanks for sharing.

[Dimitar Tsonev]

Nice. I hope this answer will make it to the top.

[d11wtq]

This was part a job interview. In these cases, you're not really expected to write "normal" code like above. They're looking for "efficient" code and a demonstration that you understand the algorithms involved.

[Natan Streppel]

@Hengameh in case j < 0, b is already exhausted, so we keep adding the remaining a elements to the answer array

[Sanjeev Dhiman]

You are just merging them; Your resultant array itself is not sorted which was a requirement.

[Muaaz salagar]

Thanks for pointing out! upvoted!

[Michael]

But why k > 0? I think it should be >= to fill all elements in array

[Shital Shah]

@Michael k is set to length of array so a s long as array is not empty, loop will execute at least once.

[Michael]

@ShitalShah sorry, i see it already. he used prefix operator, so it will go to zero first, and then execute expression.

[Kevin M]

Too "clever" and hard to read in my mind. I prefer easier to read code especially since you aren't really achieving much of any performance improvement with this code.

[Kevin M]

The question stipulated that the arrays are already in sorted order. If the arrays could be very large, this solution would grind to a halt and perform poorly. So sure you'd get the required end results, but the app would not perform and you would not get the job if I were interviewing.

[Shital Shah]

@Kevin - yes, this might look "too clever" at first but this pattern occurs fairly often. Once you get used to it, you can just apply it out of memory.

[Yan Khonski]

plus point for Notice, and a[i] >= b[j] instead of a[i] > b[j]. This guarantees "stability"

[Tomato]

@will System.arrayCopy() is stupidly fast as it uses CPU-optimised memcpy calls. So there's scope to improve performance by copying chunks. There's also scope to binary search for the boundaries.

[Eric B. Ridge]

Thanks for the inspiration. Easy to generalize to merge N arrays of M length. Doesn't fit on 1 line tho. :(

[Tatarize]

For this enhancement it would be better to check where the first element would fall in the second array with a binarysearch, then arraycopy that data to begin. Then in the case that one of those checks is true, it would just have arraycopy everything then arraycopy the ternary and you get the same result. But, in the case of a tiny bit of overlap, you only need to do the proper algorithm during the overlap and no other time. Since you're stuck with O(n) using some quick O(logn) command beforehand isn't going to cost anything.

[Tatarize]

The Array.sort() function uses TimSort which very much will find the sorted runs and apply a merge sort on them. Oddly enough, this code can't really even be faulted for "not efficient" it will actually fall into finishing in O(n) time because of the sorted runs. You can run a bunch of benchmarks on it, odds are good it'll beat the OP code quite often.

[greybeard]

Use a for loop to merge the lines declaring the loop variables and loop control. Use double blank lines sparingly - looks uncalled for between the symmetrical "tail copies".

[greybeard]

@Ahmedov: I do not understand why this answer got negative votes does it answer Is there a more efficient way to do this?

[greybeard]

(I have doubts about the method name.)

[greybeard]

What does this copy a[mid+1 .. hi] to aux for?

[greybeard]

What is the saving grace of this? It can be shrunk to for (int i, j, k = i = j = 0 ; k < c.length ; ) c[k++] = b.length <= j || i < a.length && a[i] < b[j] ? a[i++] : b[j++];. How does it differ from Andrew's 2014 answer?

[greybeard]

bulk copying the elements once over to (skilfully) use a sentinel…

[greybeard]

Confusing for naming the index into arr2 not ind2, but temp.

[greybeard]

Upvoted for starting to do something about the symmetry, but why stop there? Use galloping search, have it return the index after equal keys. Use array copy if more than 3 elements, only. Note that after that copy, nothing changed but a) the starting index in one input and the output array b) your knowledge about which "next" element is smaller.

[greybeard]

Since the question doesn't assume any specific language from 2011/5/11/19:43, it is tagged java.

[Ahmadov]

@greybeard - yes it does. The OP didn't specify what exactly he means by efficiency. Is it efficiency in terms of how complicated the code is, how many lines it needs to execute, or is it efficiency in terms of memory consumption, or is it efficiency based on the CPU cycles? Here, Sudhir provided a solution that is much more compact and "more efficient" if all you have a tiny Array. Remember, "premature optimization is the root of all evil".

[Tatarize]

That is totally what the implemented Arrays.sort does. It's notably at worst a merge sort. I think they swap 2 elements where needed but fall into arraycopy for more than 2 elements. I'm unsure as to whether you'd check for the next element linearly or binary search into it. There'd be a pretty big advantage to speculatively checking if you could gallop a larger distance if you could gallop that distance. Like check 8 ahead, and if you can copy that you saved yourself 7 operations of things you don't need to look at.

[Tatarize]

@greybeard ... and done. Also went backwards so I could reuse the same memory.

[Tatarize]

Especially if you can use the sorted nature to skip most of the entries and never compare them. You can actually beat O(n).

[greybeard]

Good thing you motivated going ballistic. Going to have a closer look after daytime time-sinks.

[greybeard]

That is totally what the implemented Arrays.sort does (That: from the first revision of your answer - or - from my Feb 19 comment?) - can't find either in Sunsoft's JDK 8: which implementation of Arrays.sort are you referring to?

[Tatarize]

I looked down the source code for sort at one point and ran into the Java implementation of TimSort which seemed to do that sort of gallop merge thing. docjar.com/html/api/java/util/TimSort.java.html

[Tatarize]

TimSort also tends to do the merging with the galloping threshold triggered by the length of the data. Beyond just making sure the data isn't checked twice, it doesn't trigger if the data consistently is going back and forth, only when one of the merge runs is consistently long enough to invoke the gallop.

[Tatarize]

As is my version does seem to hit the edge condition. It checked the previous iteration, then found it failed, but then categorically can end up rechecking that value as the low within the binary search when it should actually check previousiteration-1 (galloping backwards) as previousiteration was explicitly checked. Though the binary search does exclusive at the high end and since I went backwards it's a bit ambiguous, and shouldn't bother the binary search if the permitted range only allows one answer. It works, but I think I have a couple possible unneeded double-checks.

[John Smith]

The algorithm is slower than one suggested by Mike Saull, since you have more comparisons. Can't tell right now if it will always affect your algorithm, or for specific cases, but it will.

[Shital Shah]

@JohnSmith Boolean short circuit should take care of comparisons. Did you do any bench marking?

[John Smith]

@ShitalShah I have not done benchmarks, but just look at the code and imagine that the whole array b is above array a. Then b will be placed first. Then the array a is being placed. In your case placing array a requires two checks k > 0 and j < 0, but the check j<0 is not needed. once one array array is exhausted, there is no need in checking it again and again. the first code does not have this problem - if one array is exhausted only one check is performed.

[dark_ruby]

your solution does not take advantage of the fact lists are already sorted, and its runtime is not O(n), since .sort() is O(n log n) at best

[Mickey Donald]

I gave the exact same answer in my interview and I think the interviewer didn’t look happy!