Merge k sorted arrays | Set 1 | Javascript program to merge k sorted arrays of size n each . ; Merge arr1 [ 0. . n1 - 1 ] and arr2 [ 0. . n2 - 1 ] into arr3 [ 0. . n1 + n2 - 1 ] ; Traverse both array ; Check if current element of first array is smaller than current element of second array . If yes , store first array element and increment first array index . Otherwise do same with second array ; Store remaining elements of first array ; Store remaining elements of second array ; A utility function to print array elements ; This function takes an array of arrays as an argument and all arrays are assumed to be sorted . It merges them together and prints the final sorted output . ; If one array is in range ; If only two arrays are left them merge them ; Output arrays ; Divide the array into halves ; Merge the output array ; Driver code Change n at the top to change number of elements in an array
let n = 4 function mergeArrays ( arr1 , arr2 , n1 , n2 , arr3 ) { let i = 0 , j = 0 , k = 0 ; while ( i < n1 && j < n2 ) { if ( arr1 [ i ] < arr2 [ j ] ) arr3 [ k ++ ] = arr1 [ i ++ ] ; else arr3 [ k ++ ] = arr2 [ j ++ ] ; } while ( i < n1 ) arr3 [ k ++ ] = arr1 [ i ++ ] ; while ( j < n2 ) arr3 [ k ++ ] = arr2 [ j ++ ] ; } function printArray ( arr , size ) { for ( let i = 0 ; i < size ; i ++ ) document . write ( arr [ i ] + " " ) ; } function mergeKArrays ( arr , i , j , output ) { if ( i == j ) { for ( let p = 0 ; p < n ; p ++ ) output [ p ] = arr [ i ] [ p ] ; return ; } if ( j - i == 1 ) { mergeArrays ( arr [ i ] , arr [ j ] , n , n , output ) ; return ; } let out1 = new Array ( n * ( ( ( i + j ) / 2 ) - i + 1 ) ) let out2 = new Array ( n * ( j - ( ( i + j ) / 2 ) ) ) ; mergeKArrays ( arr , i , ( i + j ) / 2 , out1 ) ; mergeKArrays ( arr , ( i + j ) / 2 + 1 , j , out2 ) ; mergeArrays ( out1 , out2 , n * ( ( ( i + j ) / 2 ) - i + 1 ) , n * ( j - ( ( i + j ) / 2 ) ) , output ) ; } let arr = [ [ 2 , 6 , 12 , 34 ] , [ 1 , 9 , 20 , 1000 ] , [ 23 , 34 , 90 , 2000 ] ] ; let k = arr . length ; let output = new Array ( n * k ) ; mergeKArrays ( arr , 0 , 2 , output ) ; document . write ( " " + " " ) ; printArray ( output , n * k ) ;