In | Merges two subarrays of arr [ ] . First subarray is arr [ l . . m ] Second subarray is arr [ m + 1. . r ] Inplace Implementation ; If the direct merge is already sorted ; Two pointers to maintain start of both arrays to merge ; If element 1 is in right place ; Shift all the elements between element 1 element 2 , right by 1. ; Update all the pointers ; l is for left index and r is right index of the sub - array of arr to be sorted ; Same as ( l + r ) / 2 , but avoids overflow for large l and r ; Sort first and second halves ; Function to print an array ; Driver code
function merge ( arr , start , mid , end ) { let start2 = mid + 1 ; if ( arr [ mid ] <= arr [ start2 ] ) { return ; } while ( start <= mid && start2 <= end ) { if ( arr [ start ] <= arr [ start2 ] ) { start ++ ; } else { let value = arr [ start2 ] ; let index = start2 ; while ( index != start ) { arr [ index ] = arr [ index - 1 ] ; index -- ; } arr [ start ] = value ; start ++ ; mid ++ ; start2 ++ ; } } } function mergeSort ( arr , l , r ) { if ( l < r ) { let m = l + Math . floor ( ( r - l ) / 2 ) ; mergeSort ( arr , l , m ) ; mergeSort ( arr , m + 1 , r ) ; merge ( arr , l , m , r ) ; } } function printArray ( A , size ) { let i ; for ( i = 0 ; i < size ; i ++ ) document . write ( A [ i ] + " " ) ; document . write ( " " ) ; } let arr = [ 12 , 11 , 13 , 5 , 6 , 7 ] ; let arr_size = arr . length ; mergeSort ( arr , 0 , arr_size - 1 ) ; printArray ( arr , arr_size ) ;