Divide and conquer strategy to merge multiple sorted arrays

Question

Using divide and conquer strategy how can I merg k sorted arrays each with n elements into a single array of k*n elements?

Understanding so far: I got some understanding about the steps to do Divide and conquer like :

Divide the list of arrays in two lists, each of k/2 arrays. Recursively merge the arrays within the 2 lists and finally merge the resulting 2 sorted arrays into the output array.

Some Ideas and help needed !!

public int[] merge(int[][] arrays){
int k = arrays.length;
int n = arrays[0].length;
if size(arrays) == 1:
return arrays.pop()
else
// For longer lengths split the array into two
  int half = arrays.length / 2;
  int[] first_Half = new int[half];
  int[] second_Half = new int[lists.length - half];  
  return merge(merge(first_half),merge(second_half));

I tried passing the 2-Dim array as List of lists and changed my first and second half into 2 Dim. array as advised but I am getting error : "method kWayMerge(List<List>) in the type Merge is not applicable for the arguments (int[][]) on kWayMerge method

Below are the changes made and For regular merge can i use Arrays.copyOf or clone() method?

// solve the problem separately in each sub-array
            List a = kWayMerge(firstHalf);

// K-merge operation using divide and conquer strategy

     public int[] kWayMerge(List<List>array){ // gets a list of lists as input 
            int[][] firstHalf; int[][] secondHalf;
            if(array.size() == 1) return null; // if currently have 1 array, return it - stop clause
    else {
        int half = array.size()/2;
        firstHalf = new int[half][];
        secondHalf = new int[array.size()-half][];
        // solve the problem separately in each sub-array
        List a = kWayMerge(firstHalf);

    }
     return merge((firstHalf ),(secondHalf));   
}

public int[] merge(int[][] arr1, int[][] arr2) {

    return null;
}

currently I am trying to test the algorithm but I am getting error on the last merge which ask to change the parameter of merge method from 2-Dim to single Dim however I want to pass 2-Dim array — Ka Mal

amit amit · Accepted Answer · 2015-08-26T06:27:41

A divide and conquer approach would be to have a recursive function k-way-merge(), that gets a list of lists as input, and at each step:

If you currently have 1 array, return it (stop clause)
Otherwise, split the list of lists to two, and for each half - recursively invoke k-way-merge(). merge the two resulting lists.

The main aspect you need to change in your code is in:

  int[] first_Half = new int[half];
  int[] second_Half = new int[lists.length - half];

Here, you need first_half and second_half to be int[][], as they are actually list of lists.

In addition, in the last line:

return merge(merge(first_half),merge(second_half));

Note that the outer merge() is different, it's not a recursive call - but a call to "regular" merge(), that merges two arrays into one (as the logic on how to do it is missing from the code, I assume you have such merge() implemented).

Other than that, the approach looks correct, but a bit inefficient, since you copy the int[][] object every iteration, rather than using indices to "remember where you are".

Divide and conquer strategy to merge multiple sorted arrays

1 Answers