1
\$\begingroup\$

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 
\$\endgroup\$
  • \$\begingroup\$ Is there any performance requirement, or does it just need to give the correct answer? \$\endgroup\$ – JS1 Nov 16 '16 at 18:48
  • \$\begingroup\$ @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. \$\endgroup\$ – Levent Divilioglu Nov 16 '16 at 18:53
  • \$\begingroup\$ You might want to look at this other codereview question, which does the same thing in a faster but more complicated way. \$\endgroup\$ – JS1 Nov 16 '16 at 18:59
  • \$\begingroup\$ @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. \$\endgroup\$ – Levent Divilioglu Nov 16 '16 at 19:03
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$
  • 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);
    
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.