Significant Inversions in an Array | Java implementation of the above approach ; Function that sorts the input array and returns the number of inversions in the array ; 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 the inversions in the left - part , the right - part and the number of inversions in merging ; Merge the two parts ; Function that merges the two sorted arrays and returns the inversion count in the arrays ; i is the index for the left subarray ; j is the index for the right subarray ; k is the index for the resultant merged subarray ; First pass to count number of significant inversions ; i is the index for the left subarray ; j is the index for the right subarray ; k is the index for the resultant merged subarray ; Second pass to merge the two sorted arrays ; Copy the remaining elements of the left subarray ( if there are any ) to temp ; Copy the remaining elements of the right subarray ( if there are any ) to temp ; Copy back the merged elements to the original array ; Driver code
class GFG { static int mergeSort ( int arr [ ] , int array_size ) { int temp [ ] = new int [ array_size ] ; return _mergeSort ( arr , temp , 0 , array_size - 1 ) ; } static int _mergeSort ( int arr [ ] , int temp [ ] , int left , int right ) { int mid , inv_count = 0 ; if ( right > left ) { mid = ( 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 ; } static int merge ( int arr [ ] , int temp [ ] , int left , int mid , int right ) { int i , j , k ; int inv_count = 0 ; i = left ; j = mid ; k = left ; while ( ( i <= mid - 1 ) && ( j <= right ) ) { if ( arr [ i ] > 2 * arr [ j ] ) { inv_count += ( mid - i ) ; j ++ ; } else { i ++ ; } } 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 ++ ] ; } } 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 ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 20 , 6 , 4 , 5 } ; int n = arr . length ; System . out . println ( mergeSort ( arr , n ) ) ; } }