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 

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);