Java Program to Implement K Way Merge Algorithm

This is a Java Program to Implement K Way Merge Algorithm. K Way Merge Algorithm is used to merge K sorted arrays of size N into a single array.

Here is the source code of the Java Program to Implement K Way Merge Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  * Java Program to Implement K Way Merge Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class KWayMerge **/
  8. public class KWayMerge
  9. {
  10.     /** Function to merge arrays **/
  11.     private int[] merge(int[][] arr) 
  12.     {
  13.         int K = arr.length;
  14.         int N = arr[0].length;
  15.  
  16.         /** array to keep track of non considered positions in subarrays **/
  17.         int[] curPos = new int[K];
  18.  
  19.         /** final merged array **/
  20.         int[] mergedArray = new int[K * N];
  21.         int p = 0;
  22.  
  23.         while (p < K * N)
  24.         {
  25.             int min = Integer.MAX_VALUE;
  26.             int minPos = -1;
  27.             /** search for least element **/
  28.             for (int i = 0; i < K; i++)
  29.             {
  30.                 if (curPos[i] < N)
  31.                 {
  32.                     if (arr[i][curPos[i]] < min)
  33.                     {
  34.                         min = arr[i][curPos[i]];
  35.                         minPos = i;
  36.                     }
  37.                 }                
  38.             }
  39.             curPos[minPos]++;            
  40.             mergedArray[p++] = min;
  41.         }
  42.         return mergedArray;
  43.     }
  44.  
  45.     /** Main method **/
  46.     public static void main(String[] args) 
  47.     {
  48.         Scanner scan = new Scanner( System.in );        
  49.         System.out.println("K Way Merge Test\n");
  50.  
  51.         /** Accept k and n **/
  52.         System.out.println("Enter K and N");
  53.         int K = scan.nextInt();
  54.         int N = scan.nextInt();
  55.  
  56.         int[][] arr = new int[K][N];
  57.         /** Accept all elements **/
  58.         System.out.println("Enter "+ K +" sorted arrays of length "+ N);
  59.  
  60.         for (int i = 0; i < K; i++)
  61.             for (int j = 0; j < N; j++)
  62.                 arr[i][j] = scan.nextInt();
  63.  
  64.         KWayMerge kwm = new KWayMerge();
  65.  
  66.         int[] mergedArray = kwm.merge(arr);
  67.         /** Print merged array **/
  68.         System.out.println("\nMerged Array : ");
  69.         for (int i = 0; i < mergedArray.length; i++)
  70.             System.out.print(mergedArray[i] +" ");
  71.         System.out.println(); 
  72.  
  73.     }    
  74. }

K Way Merge Test
 
Enter K and N
5 4
Enter 5 sorted arrays of length 4
2 4 6 19
1 20 35 67
3 5 7 11
45 46 47 48
3 9 100 200
 
Merged Array :
1 2 3 3 4 5 6 7 9 11 19 20 35 45 46 47 48 67 100 200
 
 
 
K Way Merge Test
 
Enter K and N
4 5
Enter 4 sorted arrays of length 5
2 4 6 19 94
2 8 5 19 63
3 5 7 11 13
1 10 25 50 100
 
Merged Array :
1 2 2 3 4 5 6 7 8 5 10 11 13 19 19 25 50 63 94 100
 
 
 
K Way Merge Test
 
Enter K and N
3 10
Enter 3 sorted arrays of length 10
3 6 9 12 15 18 21 24 27 30
2 5 8 11 14 17 20 23 26 29
1 4 7 10 13 16 19 22 25 28
 
Merged Array :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.