algorithm - K-way merge operation for merge sort -

i have k sorted arrays, each n elements, , need combine them single sorted array of k*n elements.

how implement merging procedure merge sort, starting first 2 , next 1 , on?

this have far.

// implementing function merge arrays (merge procedure merge sort)        public  int[] merge(int[][] array){         int k = array.length;         int n = array[0].length;  // final merged array          int[] mergedarray = new int[k*n];         return mergedarray;          }      public static void main(string[]args){     merge obj = new merge(); int[][] data= new int[][]{{2, 9, 15, 20},                               {6, 8, 9, 19},                               {5, 10, 18, 22},                               {8, 12, 15, 26}};     int[] mergedarraytest = obj.merge(data);     //printarray(mergedarraytest);   } 

instead of merging sub-arrays 2 @ time, can merge k @ once.

• make array of indices each sub-array. each index zero.
• on each 1 of k*n iterations fill merged array, consider each sub-array's value @ respective index , remember minimum value. (skip index if has reached end of sub-array.)
• increment index pointed minimum value.

this it:

// k-way merge operation public int[] merge(int[][] array){   int k = array.length;   int n = array[0].length;    int[] mergedarray = new int[k*n];   int[] indices = new int[k];   (int = 0; < mergedarray.length; ++i) {      int bestvalue = -1, bestindex = -1;     (int j = 0; j < indices.length; ++j) {        int index = indices[j];       if (index < n && (bestvalue == -1 || array[j][index] < bestvalue)) {          bestvalue = array[j][index];         bestindex = j;       }      }      mergedarray[i] = bestvalue;     indices[bestindex] += 1;   }    return mergedarray; } 

you can make approach more efficient removing indices have reached end of sub-array. however, still leaves running time in o(nk²) because o(k) indices scanned nk times.

we can make asymptotic improvement in running time storing indices in min-heap uses value @ each index key. k indices, size of heap never exceeds k. in each of nk iterations, pop heap , push @ 1 element on. these heap operations each cost o(log k), total running time o(nk log k).

import java.lang.*; import java.util.*; import java.io.*;  class candidate {   int id, index, value;   candidate(int id, int index, int value) {     this.id = id;     this.index = index;     this.value = value;   } }  class heap {   arraylist<candidate> stack = new arraylist<candidate>();    void push(candidate current) {     // add last position in heap.     stack.add(current);     // bubble up.     int n = stack.size(),         pos = n - 1;     while (pos != 0) {       int parent = (pos - 1) / 2;       if (stack.get(parent).value <= current.value) {         return;       }       stack.set(pos, stack.get(parent));       stack.set(parent, current);     }   }    candidate pop() {     // top of heap.     if (stack.size() == 0) {       return null;     }     candidate result = stack.get(0);     int n = stack.size();     if (n == 1) {       stack.remove(0);       return result;     }     // swap last element top.     stack.set(0, stack.get(--n));     candidate current = stack.get(0);     stack.remove(n);     // bubble down.     int pos = 0;     while (true) {       int left = 2 * pos + 1;       if (left >= n) {         return result;       }       int right = left + 1,           swapto = -1;       if (current.value <= stack.get(left).value) {         if (right == n || current.value <= stack.get(right).value) {           return result;         }         swapto = right;       } else {         if (right != n && stack.get(left).value > stack.get(right).value) {           swapto = right;         } else {           swapto = left;         }       }       stack.set(pos, stack.get(swapto));       stack.set(swapto, current);       pos = swapto;     }   } }  public class merge {    // k-way merge   public  int[] merge(int[][] array){     int k = array.length;     int n = array[0].length;      int[] mergedarray = new int[k*n];      // initialize heap subarray number, index, , value.     heap indexheap = new heap();     (int = 0; < k; ++i) {       indexheap.push(new candidate(i, 0, array[i][0]));     }      (int = 0; < mergedarray.length; ++i) {       // minimum value heap , augment merged array.       candidate best = indexheap.pop();       mergedarray[i] = best.value;       // increment index. if it's still valid, push onto heap.       if (++best.index < array[best.id].length) {         best.value = array[best.id][best.index];         indexheap.push(best);       }     }      // print out merged array testing purposes.     (int = 0; < mergedarray.length; ++i) {       system.out.print(mergedarray[i] + " ");     }     system.out.println();     return mergedarray;   }    public static void main(string[]args){     merge merge = new merge();     int[][] data= new int[][]{{2, 9, 15, 20},                               {6, 8, 9, 19},                               {5, 10, 18, 22},                               {8, 12, 15, 26}};     int[] mergedarraytest = merge.merge(data);   } }