Combining sorted arrays without using the sort function in Java

Question

I have a task question that I need to solve without using the 'sort' command. I would be grateful for any advice.

QUESTION: Suppose you have two arrays of ints, arr1 and arr2, each of which contains integers sorted in ascending order.

Write a static method called merge that receives these two arrays with parameters and returns a link to a new, sorted array from int, which is the result of merging ints arr and arr2.

Answer 1

Look at the merge sort .

Answer 2

pseudo code:

1: Set two pointers to beginning of the two arrays. 2: Compare the values from the two arrays at the pointers. 3: Add the smaller value to a new array and move its pointer to the next value in the array. 4: Repeat till both pointers cross the ends of the two arrays. 

Answer 3

easy, this is the last step of the merge sort algorithm. make 2 integer variables to keep track of the index for each different input array.

Then the loop repeats as many times as there are elements adding a minimum (or maximum depending on your sort order) from the first 2 elements of the input arrays. Thus, at each iteration, the smallest possible value is added to the returned array. Just make sure your first index of input arrays is still less than the length of the first input array, if that is not the case, you know that the rest of the added items are in the second input array. Increase the index for any array from which you took the element, and then increase the index for the total array of values.

Answer 4

If you need extra points or you are bored: the relatively new Timsort algorithm uses a slightly improved merge function for the case when the data is clustered (which is relatively common). This is described at http://svn.python.org/projects/python/trunk/Objects/listsort.txt - "galloping mode" search. Galloping mode is also used in the timsort implementation for Java.