Merge K sorted Arrays

Merge K sorted Arrays

  August 19, 2017    

---

Explanation:

Here i am using a loop to merge two list and then calling merge to merge next array with previously merged List.

Another idea is to push elements into heap and add them to array.

Code:

         public static ArrayList<Integer> merge(ArrayList<Integer> arr,int[]arrays,int k)

         {

             ArrayList<Integer> nxt=new ArrayList<Integer>();

             int i=0;

             while(!arr.isEmpty() && i<k)

             {

                 if(arr.get(0) <arrays[i])

                 {

                     nxt.add(arr.remove(0));

                 }

                 else

                 nxt.add(arrays[i++]);

             }

             while(!arr.isEmpty())

             nxt.add(arr.remove(0));

             while(i<k)

             nxt.add(arrays[i++]);

             return nxt;

         }

        public static ArrayList<Integer> mergeKArrays(int[][] arrays,int k) 

          {

           ArrayList<Integer> arr=new ArrayList<Integer>();

           for(int i=0;i<k;i++)

           arr.add(arrays[0][i]);

           for(int i=1;i<k;i++)

           arr=merge(arr,arrays[i],k);

           return arr;

          }