Significant Inversions in an Array | 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
def mergeSort ( arr , array_size ) : NEW_LINE INDENT temp = [ 0 for i in range ( array_size ) ] NEW_LINE return _mergeSort ( arr , temp , 0 , array_size - 1 ) NEW_LINE DEDENT def _mergeSort ( arr , temp , left , right ) : NEW_LINE INDENT mid , inv_count = 0 , 0 NEW_LINE if ( right > left ) : NEW_LINE INDENT mid = ( right + left ) // 2 NEW_LINE inv_count = _mergeSort ( arr , temp , left , mid ) NEW_LINE inv_count += _mergeSort ( arr , temp , mid + 1 , right ) NEW_LINE inv_count += merge ( arr , temp , left , mid + 1 , right ) NEW_LINE DEDENT return inv_count NEW_LINE DEDENT def merge ( arr , temp , left , mid , right ) : NEW_LINE INDENT inv_count = 0 NEW_LINE i = left NEW_LINE j = mid NEW_LINE k = left NEW_LINE while ( ( i <= mid - 1 ) and ( j <= right ) ) : NEW_LINE INDENT if ( arr [ i ] > 2 * arr [ j ] ) : NEW_LINE INDENT inv_count += ( mid - i ) NEW_LINE j += 1 NEW_LINE DEDENT else : NEW_LINE INDENT i += 1 NEW_LINE DEDENT DEDENT i = left NEW_LINE j = mid NEW_LINE k = left NEW_LINE while ( ( i <= mid - 1 ) and ( j <= right ) ) : NEW_LINE INDENT if ( arr [ i ] <= arr [ j ] ) : NEW_LINE INDENT temp [ k ] = arr [ i ] NEW_LINE i , k = i + 1 , k + 1 NEW_LINE DEDENT else : NEW_LINE INDENT temp [ k ] = arr [ j ] NEW_LINE k , j = k + 1 , j + 1 NEW_LINE DEDENT DEDENT while ( i <= mid - 1 ) : NEW_LINE INDENT temp [ k ] = arr [ i ] NEW_LINE i , k = i + 1 , k + 1 NEW_LINE DEDENT while ( j <= right ) : NEW_LINE INDENT temp [ k ] = arr [ j ] NEW_LINE j , k = j + 1 , k + 1 NEW_LINE DEDENT for i in range ( left , right + 1 ) : NEW_LINE INDENT arr [ i ] = temp [ i ] NEW_LINE DEDENT return inv_count NEW_LINE DEDENT arr = [ 1 , 20 , 6 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( mergeSort ( arr , n ) ) NEW_LINE