How to merge two sorted arrays into a sorted array.

Problem:

You are given 2 sorted integer arrays, you need to merge these 2 arrays and result should also be sorted array. Example is below.

      static Integer[] firstList = {1,2,2,4,5,12,12,23,63,65,235,624};  
      static Integer[] secondList = {2,3,5,6,7,22,23,24,52,66,67,68,77,78,89,98};  

If above are the 2 integer lists, output would be:

Output: 1 2 2 2 3 4 5 5 6 7 12 12 22 23 23 24 52 63 65 66 67 68 77 78 89 98 235 624

This is also very good interview coding question because interviewer can access how efficiently you can merge and sort the arrays at the same time. As always there could be many solutions of this problem. This time instead of listing all not so good solutions first, I am giving only best solution.

Here it is:

1. Iterate through both the arrays until anyone reached it's full length.
2. Compare indexed elements from each array and add them to result array accordingly.
3. Iterate both the arrays for remaining elements after first iteration.
4. Add the elements from the array to result array accordingly.

1:       public static void merge2ArraysAsSortedArray() {  
2:            Integer[] resultList = new Integer[firstList.length+secondList.length];  
3:            int i=0, j=0, k=0;  
4:            while (i<firstList.length && j < secondList.length) {  
5:                 if(firstList[i] <= secondList[j]){  
6:                      resultList[k++] = firstList[i++];  
7:                 } else {  
8:                      resultList[k++] = secondList[j++];  
9:                 }  
10:            }  
11:            while (i<firstList.length) {  
12:                 resultList[k++] = firstList[i++];  
13:            }  
14:            while (j<secondList.length) {  
15:                 resultList[k++] = secondList[j++];  
16:            }  
17:            printList(resultList);  
18:       }  
19:       public static void printList(Integer[] list){  
20:            for (Integer integer : list) {  
21:                 System.out.printf("%d ",integer);  
22:            }  
23:            System.out.printf("%n");  
24:       }  

This is a good solution because time complexity of this solution is O(N) where N is the sum of lengths of both the given arrays. There is one more solution I found on internet, which is not more efficient then the first one but it's more neat and short.

Here take a look.

1:  public static void mergeArraysAsSortedArray() {  
2:            Integer[] resultList = new Integer[firstList.length+secondList.length];  
3:            int i=firstList.length-1, j=secondList.length-1, k=resultList.length;  
4:            while(k > 0){  
5:                 resultList[--k] = (j<0 || (i>=0 && firstList[i] >= secondList[j])) ? firstList[i--]: secondList[j--];  
6:            }  
7:            printList(resultList);  
8:       }  

So here they were, Let me know if anyone of you have any better solution.