Merge K sorted arrays | Set 3 ( Using Divide and Conquer Approach ) | Javascript 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 par left array ; storing data par 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
var n = 4 ; function merge ( l , r , output ) { var l_in = l * n , r_in = ( parseInt ( ( l + r ) / 2 ) + 1 ) * n ; var l_c = ( parseInt ( ( l + r ) / 2 ) - l + 1 ) * n ; var r_c = ( r - parseInt ( ( l + r ) / 2 ) ) * n ; var l_arr = Array ( l_c ) , r_arr = Array ( r_c ) ; for ( var i = 0 ; i < l_c ; i ++ ) l_arr [ i ] = output [ l_in + i ] ; for ( var i = 0 ; i < r_c ; i ++ ) r_arr [ i ] = output [ r_in + i ] ; var l_curr = 0 , r_curr = 0 ; var par = 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 [ par ] = l_arr [ l_curr ] ; l_curr ++ , par ++ ; } else { output [ par ] = r_arr [ r_curr ] ; r_curr ++ , par ++ ; } } } function divide ( l , r , output , arr ) { if ( l == r ) { for ( var i = 0 ; i < n ; i ++ ) output [ l * n + i ] = arr [ l ] [ i ] ; return ; } divide ( l , parseInt ( ( l + r ) / 2 ) , output , arr ) ; divide ( parseInt ( ( l + r ) / 2 ) + 1 , r , output , arr ) ; merge ( l , r , output ) ; } var arr = [ [ 5 , 7 , 15 , 18 ] , [ 1 , 8 , 9 , 17 ] , [ 1 , 4 , 7 , 7 ] ] ; var k = arr . length ; var output = Array ( n * k ) ; divide ( 0 , k - 1 , output , arr ) ; for ( var i = 0 ; i < n * k ; i ++ ) document . write ( output [ i ] + " " ) ;