I was being asked in an Interview to write a Java program to merge K Sorted arrays. Something like below would be the input:

int[][] kSortedArrs = { {1, 5, 6, 8},
                {2, 4, 10, 12},
                {3, 7, 9, 11},
                {13, 14, 15, 16}} ;

I knew the solution for merging two sorted arrays, so I wrote that method (mergeSortedArrs) & used it repeatedly as a solution for this problem. Code looks like the below:

    public static int[] mergeKSortedArrays(int[][] arr) {
        int[] mergedArr = new int[] {};
        for(int i=0; i < arr.length; i  ) {
            mergedArr = mergeSortedArrs(mergedArr, arr[i]);
        }
        return mergedArr;
    }

    private static int[] mergeSortedArrs(int[] arr1, int[] arr2) {
        int[] arr3 = new int[arr1.length   arr2.length];
        int i = 0;
        int j = 0;
        for (int k = 0; k < arr3.length; k  ) {
            if (i >= arr1.length) {
                arr3[k] = arr2[j  ];
                continue;
            }
            if (j >= arr2.length) {
                arr3[k] = arr1[i  ];
                continue;
            }
            arr3[k] = arr1[i] <= arr2[j] ? arr1[i  ] : arr2[j  ];
        }
        return arr3;
    }

My code worked fine, at least for the test cases that were given to me. But I want to know if this solution has any drawbacks in terms of it's correctness, because I searched on the internet but could not find a solution that is close to this solution of mine. Hence, I am a bit skeptical if I have messed up something. Kindly suggest.

CodePudding user response：

Your code is correct and solves the problem, but it's slow. Imagine you had k lists of 1 element each, your code would merge the first two, then add the third, then the fourth and so on, for a total runtime complexity of O(k^2).

If you were to instead do a single pass over the array where you merge the first with the second, the third with the fourth and so on, you would end up with k/2 sorted lists of length 2, this runs in O(k). Do this again to get k/4 lists of length 4 and so on, until you only have one list. This runs in O(k log k), which is much faster.