Number of swaps to sort when only adjacent swapping allowed | This function merges two sorted arrays and returns inversion count in the arrays . ; i is index for left subarray ; j is index for right subarray ; k is index for resultant merged subarray ; this is tricky -- see above explanation / diagram for merge ( ) ; Copy the remaining elements of left subarray ( if there are any ) to temp ; Copy the remaining elements of right subarray ( if there are any ) to temp ; Copy back the merged elements to original array ; An auxiliary recursive function that sorts the input array and returns the number of inversions in the array . ; Divide the array into two parts and call _mergeSortAndCountInv ( ) for each of the parts ; Inversion count will be sum of inversions in left - part , right - part and number of inversions in merging ; Merge the two parts ; This function sorts the input array and returns the number of inversions in the array ; Driver progra to test above functions
< ? php function merge ( & $ arr , & $ temp , $ left , $ mid , $ right ) { $ inv_count = 0 ; $ i = $ left ; $ j = $ mid ; $ k = $ left ; while ( ( $ i <= $ mid - 1 ) && ( $ j <= $ right ) ) { if ( $ arr [ $ i ] <= $ arr [ $ j ] ) $ temp [ $ k ++ ] = $ arr [ $ i ++ ] ; else { $ temp [ $ k ++ ] = $ arr [ $ j ++ ] ; $ inv_count = $ inv_count + ( $ mid - $ i ) ; } } while ( $ i <= $ mid - 1 ) $ temp [ $ k ++ ] = $ arr [ $ i ++ ] ; while ( $ j <= $ right ) $ temp [ $ k ++ ] = $ arr [ $ j ++ ] ; for ( $ i = $ left ; $ i <= $ right ; $ i ++ ) $ arr [ $ i ] = $ temp [ $ i ] ; return $ inv_count ; } function _mergeSort ( & $ arr , & $ temp , $ left , $ right ) { $ inv_count = 0 ; if ( $ right > $ left ) { $ mid = intval ( ( $ right + $ left ) / 2 ) ; $ inv_count = _mergeSort ( $ arr , $ temp , $ left , $ mid ) ; $ inv_count += _mergeSort ( $ arr , $ temp , $ mid + 1 , $ right ) ; $ inv_count += merge ( $ arr , $ temp , $ left , $ mid + 1 , $ right ) ; } return $ inv_count ; } function countSwaps ( & $ arr , $ n ) { $ temp = array_fill ( 0 , $ n , NULL ) ; return _mergeSort ( $ arr , $ temp , 0 , $ n - 1 ) ; } $ arr = array ( 1 , 20 , 6 , 4 , 5 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; echo " Number ▁ of ▁ swaps ▁ is ▁ " . countSwaps ( $ arr , $ n ) ; return 0 ; ? >