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
< ? php function nextGap ( $ gap ) { if ( $ gap <= 1 ) return 0 ; return ( $ gap / 2 ) + ( $ gap % 2 ) ; } function merge ( $ arr1 , $ arr2 , $ n , $ m ) { $ 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 ] ) { $ tmp = $ arr1 [ $ i ] ; $ arr1 [ $ i ] = $ arr1 [ $ i + $ gap ] ; $ arr1 [ $ i + $ gap ] = $ tmp ; } for ( $ j = $ gap > $ n ? $ gap - $ n : 0 ; $ i < $ n && $ j < $ m ; $ i ++ , $ j ++ ) if ( $ arr1 [ $ i ] > $ arr2 [ $ j ] ) { $ tmp = $ arr1 [ $ i ] ; $ arr1 [ $ i ] = $ arr2 [ $ j ] ; $ arr2 [ $ j ] = $ tmp ; } if ( $ j < $ m ) { for ( $ j = 0 ; $ j + $ gap < $ m ; $ j ++ ) if ( $ arr2 [ $ j ] > $ arr2 [ $ j + $ gap ] ) { $ tmp = $ arr2 [ $ j ] ; $ arr2 [ $ j ] = $ arr2 [ $ j + $ gap ] ; $ arr2 [ $ j + $ gap ] = $ tmp ; } } } echo " First ▁ Array : ▁ " ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) echo $ arr1 [ $ i ] . " ▁ " ; echo " Second Array : " for ( $ i = 0 ; $ i < $ m ; $ i ++ ) echo $ arr2 [ $ i ] . " ▁ " ; echo " STRNEWLINE " ; } $ a1 = array ( 10 , 27 , 38 , 43 , 82 ) ; $ a2 = array ( 3 , 9 ) ; $ n = sizeof ( $ a1 ) ; $ m = sizeof ( $ a2 ) ; merge ( $ a1 , $ a2 , $ n , $ m ) ; ? >