Merge Sort with O ( 1 ) extra space merge and O ( n lg n ) time [ Unsigned Integers Only ] | Javascript program to sort an array using merge sort such that merge operation takes O ( 1 ) extra space . ; Obtaining actual values ; Recursive merge sort with extra parameter , naxele ; This functions finds max element and calls recursive merge sort . ; Driver code
function merge ( arr , beg , mid , end , maxele ) { let i = beg ; let j = mid + 1 ; let k = beg ; while ( i <= mid && j <= end ) { if ( arr [ i ] % maxele <= arr [ j ] % maxele ) { arr [ k ] = arr [ k ] + ( arr [ i ] % maxele ) * maxele ; k ++ ; i ++ ; } else { arr [ k ] = arr [ k ] + ( arr [ j ] % maxele ) * maxele ; k ++ ; j ++ ; } } while ( i <= mid ) { arr [ k ] = arr [ k ] + ( arr [ i ] % maxele ) * maxele ; k ++ ; i ++ ; } while ( j <= end ) { arr [ k ] = arr [ k ] + ( arr [ j ] % maxele ) * maxele ; k ++ ; j ++ ; } for ( i = beg ; i <= end ; i ++ ) { arr [ i ] = Math . floor ( arr [ i ] / maxele ) ; } } function mergeSortRec ( arr , beg , end , maxele ) { if ( beg < end ) { let mid = Math . floor ( ( beg + end ) / 2 ) ; mergeSortRec ( arr , beg , mid , maxele ) ; mergeSortRec ( arr , mid + 1 , end , maxele ) ; merge ( arr , beg , mid , end , maxele ) ; } } function mergeSort ( arr , n ) { let maxele = Math . max ( ... arr ) + 1 ; mergeSortRec ( arr , 0 , n - 1 , maxele ) ; } let arr = [ 999 , 612 , 589 , 856 , 56 , 945 , 243 ] ; let n = arr . length ; mergeSort ( arr , n ) ; document . write ( " " ) ; for ( let i = 0 ; i < n ; i ++ ) { document . write ( arr [ i ] + " " ) ; }