Merging K Sorted Arrays

Question

My aim is to merge k different sorted array with unique elements and I want a code review about it, here is my code below which is written in java;

public class MergeDemo {
 public static void main(String[] args) {
 int[] arr1 = { 1, 2, 6, 7, 18, 19 };
 int[] arr2 = { 3, 4, 5, 8, 9 };
 int[] arr3 = { 10, 11, 12 };
 int[] arr4 = { 13, 14, 15, 20};
 int[] arr5 = { 16, 17};
 int[][] arrays = { arr1, arr2, arr3, arr4, arr5 };
 handleAnswer(arrays);
 }
 public static void handleAnswer(int[][] arrays) {
 System.out.println("List of arrays to be merged;");
 System.out.println("****************************");
 for(int i = 0; i < arrays.length; i++) {
 System.out.printf("Array [%d]: ", i);
 printArray(arrays[i]);
 }
 System.out.println("");
 System.out.println("Merged array;");
 System.out.println("*************");
 printArray(merge(arrays));
 }
 public static void printArray(int[] array) {
 for(int i = 0; i < array.length; i++)
 System.out.printf("%d ", array[i]);
 System.out.print('\n');
 }
 /*
 * Merges k sorted arrays with arbitrary lengths
 * Calls overloaded merge method with two parameters
 */
 private static int[] merge(int[][] arrays) {
 int[] mergeArray = new int[arrays[0].length];
 System.arraycopy(arrays[0], 0, mergeArray, 0, arrays[0].length);
 for(int i = 1; i < arrays.length; i++) {
 mergeArray = merge(mergeArray, arrays[i]);
 }
 return mergeArray;
 }
 /*
 * Merges two sorted arrays assuming 
 * they have unique elements
 */
 private static int[] merge(int[] arr1, int[] arr2) {
 int left = 0;
 int right = 0;
 int[] mergeArr = new int[ arr1.length + arr2.length ];
 int index = 0;
 while(index != mergeArr.length){
 if(left == arr1.length) {
 while(right != arr2.length) {
 mergeArr[index++] = arr2[right++];
 }
 } else if(right == arr2.length) {
 while(left != arr1.length) {
 mergeArr[index++] = arr1[left++];
 }
 } else {
 if(arr1[left] < arr2[right]) {
 mergeArr[index++] = arr1[left++];
 } else {
 mergeArr[index++] = arr2[right++];
 }
 }
 }
 return mergeArr;
 }
}

And sample output of the code above;

List of arrays to be merged;
****************************
Array [0]: 1 2 6 7 18 19 
Array [1]: 3 4 5 8 9 
Array [2]: 10 11 12 
Array [3]: 13 14 15 20 
Array [4]: 16 17 
Merged array;
*************
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

• JS1: Is there any performance requirement, or does it just need to give the correct answer?
• Levent Divilioglu: @JS1 Actually I'm not sure, I'm doing somebody else's homework and the instructor just asks to merge k different sorted arrays. The homework is requested after completing the lesson which that the Merge Sort is introduced.
• JS1: You might want to look at this other codereview question, which does the same thing in a faster but more complicated way.
• Levent Divilioglu: @JS1 Thanks but that solution is using PriortyQueue's and because that this homework is requested just after completing the Sorting Algo's (before the PriorityQueue is introduced), I didn't consider looking that way. I just want a code review with positive/negative critics for using a similar way to the merge sort's merge method.

Answer 1

No need to copy first array

Right now, you have this code that copies the first array into mergeArray, and then you start the merging loop:

 int[] mergeArray = new int[arrays[0].length];
 System.arraycopy(arrays[0], 0, mergeArray, 0, arrays[0].length);
 for(int i = 1; i < arrays.length; i++) {
 mergeArray = merge(mergeArray, arrays[i]);
 }

You don't actually need to do this copy. Instead, you can just do this:

 int[] mergeArray = arrays[0];
 for(int i = 1; i < arrays.length; i++) {
 mergeArray = merge(mergeArray, arrays[i]);
 }

Reduce bounds checking

Your merging function is correct, but it checks both the left and right bounds on each iteration:

 while(index != mergeArr.length){
 if(left == arr1.length) {
 while(right != arr2.length) {
 mergeArr[index++] = arr2[right++];
 }
 } else if(right == arr2.length) {
 while(left != arr1.length) {
 mergeArr[index++] = arr1[left++];
 }
 } else {
 if(arr1[left] < arr2[right]) {
 mergeArr[index++] = arr1[left++];
 } else {
 mergeArr[index++] = arr2[right++];
 }
 }
 }

It would be slightly faster to only checking the bound that was moved:

 while (true) {
 if (arr1[left] < arr2[right]) {
 mergeArr[index++] = arr1[left++];
 if (left == arr1.length) {
 while (right != arr2.length) {
 mergeArr[index++] = arr2[right++];
 }
 break;
 }
 } else {
 mergeArr[index++] = arr2[right++];
 if (right == arr2.length) {
 while (left != arr1.length) {
 mergeArr[index++] = arr1[left++];
 }
 break;
 }
 }
 }

If you make this change, you also need to add a check before the loop that handles the case where one or both of the arrays had length 0.

Answer 2

• The most important feature of merge sort is stability: equal elements retail their original order. The logic expressed as

   if(arr1[left] < arr2[right]) {
   mergeArr[index++] = arr1[left++];
   } else {
   mergeArr[index++] = arr2[right++];
   }
  

  is a typical mistake: in case the elements compare equal, the element from arr2 is merged first. Stability is lost.

• The merge loop is suboptimal. On each iteration is tests three termination conditions - it is enough to test for two.

• No naked loops, please. Any loop represent an important algorithm, and deserves a name.

  All that said, consider

   while (left < arr1.length && right < arr2.length) {
   if (arr1[left] <= arr2[right]) {
   mergeArr[index++] = arr1[left++];
   } else {
   mergeArr[index++] = arr2[right++];
   }
   }
   copy(mergeArr, index, arr1, left);
   copy(mergeArr, index, arr2, right);