Merge Sort | Merges two subarrays of arr [ ] . First subarray is arr [ l . . m ] Second subarray is arr [ m + 1. . r ] ; Find sizes of two subarrays to be merged ; Create temp arrays ; Copy data to temp arrays L [ ] and R [ ] ; Merge the temp arrays Initial indexes of first and second subarrays ; Initial index of merged subarray ; Copy the remaining elements of L [ ] , if there are any ; Copy the remaining elements of R [ ] , if there are any ; l is for left index and r is right index of the sub - array of arr to be sorted ; returns recursively ; Sort first and second halves ; Merge the sorted halves ; Function to print an array ; Driver code
function merge ( arr , l , m , r ) { var n1 = m - l + 1 ; var n2 = r - m ; var L = new Array ( n1 ) ; var R = new Array ( n2 ) ; for ( var i = 0 ; i < n1 ; i ++ ) L [ i ] = arr [ l + i ] ; for ( var j = 0 ; j < n2 ; j ++ ) R [ j ] = arr [ m + 1 + j ] ; var i = 0 ; var j = 0 ; var k = l ; while ( i < n1 && j < n2 ) { if ( L [ i ] <= R [ j ] ) { arr [ k ] = L [ i ] ; i ++ ; } else { arr [ k ] = R [ j ] ; j ++ ; } k ++ ; } while ( i < n1 ) { arr [ k ] = L [ i ] ; i ++ ; k ++ ; } while ( j < n2 ) { arr [ k ] = R [ j ] ; j ++ ; k ++ ; } } function mergeSort ( arr , l , r ) { if ( l >= r ) { return ; } var m = l + parseInt ( ( r - l ) / 2 ) ; mergeSort ( arr , l , m ) ; mergeSort ( arr , m + 1 , r ) ; merge ( arr , l , m , r ) ; } function printArray ( A , size ) { for ( var i = 0 ; i < size ; i ++ ) document . write ( A [ i ] + " " ) ; } var arr = [ 12 , 11 , 13 , 5 , 6 , 7 ] ; var arr_size = arr . length ; document . write ( " " ) ; printArray ( arr , arr_size ) ; mergeSort ( arr , 0 , arr_size - 1 ) ; document . write ( " " ) ; printArray ( arr , arr_size ) ;