Merge K sorted arrays | Set 3 ( Using Divide and Conquer Approach ) | PHP 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 ; input 2D - array ; Number of arrays ; Output array ; Print merged array
< ? php $ n = 4 ; function merge ( $ l , $ r , & $ output ) { global $ n ; $ l_in = $ l * $ n ; $ r_in = ( ( int ) ( ( $ l + $ r ) / 2 ) + 1 ) * $ n ; $ l_c = ( int ) ( ( ( ( $ l + $ r ) / 2 ) - $ l + 1 ) * $ n ) ; $ r_c = ( $ r - ( int ) ( ( $ l + $ r ) / 2 ) ) * $ n ; $ l_arr = array_fill ( 0 , $ l_c , 0 ) ; $ r_arr = array_fill ( 0 , $ r_c , 0 ) ; for ( $ i = 0 ; $ i < $ l_c ; $ i ++ ) $ l_arr [ $ i ] = $ output [ $ l_in + $ i ] ; for ( $ i = 0 ; $ i < $ r_c ; $ i ++ ) $ r_arr [ $ i ] = $ output [ $ r_in + $ i ] ; $ l_curr = 0 ; $ r_curr = 0 ; $ 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 ++ ; } } } function divide ( $ l , $ r , & $ output , $ arr ) { global $ n ; if ( $ l == $ r ) { for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ output [ $ l * $ n + $ i ] = $ arr [ $ l ] [ $ i ] ; return ; } divide ( $ l , ( int ) ( ( $ l + $ r ) / 2 ) , $ output , $ arr ) ; divide ( ( int ) ( ( $ l + $ r ) / 2 ) + 1 , $ r , $ output , $ arr ) ; merge ( $ l , $ r , $ output ) ; } $ arr = array ( array ( 5 , 7 , 15 , 18 ) , array ( 1 , 8 , 9 , 17 ) , array ( 1 , 4 , 7 , 7 ) ) ; $ k = count ( $ arr ) ; $ output = array_fill ( 0 , $ n * $ k , 0 ) ; divide ( 0 , $ k - 1 , $ output , $ arr ) ; for ( $ i = 0 ; $ i < $ n * $ k ; $ i ++ ) print ( $ output [ $ i ] . " ▁ " ) ; ? >