Merge K sorted arrays | Set 3 ( Using Divide and Conquer Approach ) | Java program to merge K sorted arrays ; Function to perform merge operation ; To store the starting point of left and right array ; to store the size of left and right array ; array to temporarily store left and right array ; storing data in left array ; storing data in right array ; to store the current index of temporary left and right array ; to store the current index for output array ; two pointer merge for two sorted arrays ; Code to drive merge - sort and create recursion tree ; base step to initialize the output array before performing merge operation ; to sort left half ; to sort right half ; merge the left and right half ; Driver Code ; input 2D - array ; Number of arrays ; Output array ; Print merged array
import java . util . * ; class GFG { static int n = 4 ; static void merge ( int l , int r , int [ ] output ) { int l_in = l * n , r_in = ( ( l + r ) / 2 + 1 ) * n ; int l_c = ( ( l + r ) / 2 - l + 1 ) * n ; int r_c = ( r - ( l + r ) / 2 ) * n ; int l_arr [ ] = new int [ l_c ] , r_arr [ ] = new int [ r_c ] ; for ( int i = 0 ; i < l_c ; i ++ ) l_arr [ i ] = output [ l_in + i ] ; for ( int i = 0 ; i < r_c ; i ++ ) r_arr [ i ] = output [ r_in + i ] ; int l_curr = 0 , r_curr = 0 ; int in = l_in ; while ( l_curr + r_curr < l_c + r_c ) { if ( r_curr == r_c || ( l_curr != l_c && l_arr [ l_curr ] < r_arr [ r_curr ] ) ) { output [ in ] = l_arr [ l_curr ] ; l_curr ++ ; in ++ ; } else { output [ in ] = r_arr [ r_curr ] ; r_curr ++ ; in ++ ; } } } static void divide ( int l , int r , int [ ] output , int arr [ ] [ ] ) { if ( l == r ) { for ( int i = 0 ; i < n ; i ++ ) output [ l * n + i ] = arr [ l ] [ i ] ; return ; } divide ( l , ( l + r ) / 2 , output , arr ) ; divide ( ( l + r ) / 2 + 1 , r , output , arr ) ; merge ( l , r , output ) ; } public static void main ( String [ ] args ) { int arr [ ] [ ] = { { 5 , 7 , 15 , 18 } , { 1 , 8 , 9 , 17 } , { 1 , 4 , 7 , 7 } } ; int k = arr . length ; int [ ] output = new int [ n * k ] ; divide ( 0 , k - 1 , output , arr ) ; for ( int i = 0 ; i < n * k ; i ++ ) System . out . print ( output [ i ] + " ▁ " ) ; } }