Merging sorted arrays without using a sort function in Java

I开发者_StackOverflow中文版 have an assignment question that I need to solve without using a 'sort' commmand. I would appreciate any advice.

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

Write a static method named merge that recieves these two arrays a parameters and returns a reference to a new, sorted array of ints that is the result of merging the ints of arr and arr2.

---

Look into merge sort.

---

Pseudocode:

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.

---

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

Then loop through as many times as there are elements adding the minimum(or maximum depending on your sort order) out of the 2 first elements in the input arrays. This way on each iteration the smallest possible value is added to the return array. Just make sure to check that your first input array index is still less than the first input array length, if it is not then you know the rest of the elements to add are in the second input array. Increment the index for whichever array you took the element from, and increment your index for the overall array of values then.

---

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