Efficiently merging two sorted arrays with O ( 1 ) extra space | Function to find next gap . ; comparing elements in the first array . ; comparing elements in both arrays . ; comparing elements in the second array . ; Driver code ; Function Call
function nextGap ( gap ) { if ( gap <= 1 ) return 0 ; return parseInt ( gap / 2 , 10 ) + ( gap % 2 ) ; } function merge ( arr1 , arr2 , n , m ) { let i , j , gap = n + m ; for ( gap = nextGap ( gap ) ; gap > 0 ; gap = nextGap ( gap ) ) { for ( i = 0 ; i + gap < n ; i ++ ) if ( arr1 [ i ] > arr1 [ i + gap ] ) { let temp = arr1 [ i ] ; arr1 [ i ] = arr1 [ i + gap ] ; arr1 [ i + gap ] = temp ; } for ( j = gap > n ? gap - n : 0 ; i < n && j < m ; i ++ , j ++ ) if ( arr1 [ i ] > arr2 [ j ] ) { let temp = arr1 [ i ] ; arr1 [ i ] = arr2 [ j ] ; arr2 [ j ] = temp ; } if ( j < m ) { for ( j = 0 ; j + gap < m ; j ++ ) if ( arr2 [ j ] > arr2 [ j + gap ] ) { let temp = arr2 [ j ] ; arr2 [ j ] = arr2 [ j + gap ] ; arr2 [ j + gap ] = temp ; } } } } let a1 = [ 10 , 27 , 38 , 43 , 82 ] ; let a2 = [ 3 , 9 ] ; merge ( a1 , a2 , a1 . length , a2 . length ) ; document . write ( " " ) ; for ( let i = 0 ; i < a1 . length ; i ++ ) { document . write ( a1 [ i ] + " " ) ; } document . write ( " " ) ; document . write ( " " ) ; for ( let i = 0 ; i < a2 . length ; i ++ ) { document . write ( a2 [ i ] + " " ) ; }