title: Divide and conquer strategy to merge multiple sorted arrays
body: <p>Using <strong>divide and conquer strategy</strong> how can I merg k sorted arrays each with n elements into a single array of k*n elements?</p>
  
  <p><strong>Understanding so far:</strong> I got some understanding about the steps to do Divide and conquer like :</p>
  
  <p>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. </p>
  
  <p>Some Ideas and help needed !!</p>
  
  <pre><code>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));
  </code></pre>
  
  <hr>
  
  <p>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 <code>kWayMerge(List&lt;List&gt;)</code> in the type Merge is not applicable for the arguments <code>(int[][])</code> on kWayMerge method</p>
  
  <p>Below are the changes made and For regular merge can i use <code>Arrays.copyOf</code> or <code>clone()</code> method?</p>
  
  <pre><code>// solve the problem separately in each sub-array
              List a = kWayMerge(firstHalf);
  
  // K-merge operation using divide and conquer strategy
  
       public int[] kWayMerge(List&lt;List&gt;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;
  }
  </code></pre>