human
Give me a code to significant Inversions in an Array and the other steps required given the following:
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"
How can the above be solved in Python?
assistant
#Here is code to significant Inversions in an Array and the other steps required.
 def mergeSort ( arr , array_size ) :
	temp = [ 0 for i in range ( array_size ) ]
	return _mergeSort ( arr , temp , 0 , array_size - 1 )
def _mergeSort ( arr , temp , left , right ) :
	mid , inv_count = 0 , 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
def merge ( arr , temp , left , mid , right ) :
	inv_count = 0
	i = left
	j = mid
	k = left
	while ( ( i <= mid - 1 ) and ( j <= right ) ) :
		if ( arr [ i ] > 2 * arr [ j ] ) :
			inv_count += ( mid - i )
			j += 1
		else :
			i += 1
	i = left
	j = mid
	k = left
	while ( ( i <= mid - 1 ) and ( j <= right ) ) :
		if ( arr [ i ] <= arr [ j ] ) :
			temp [ k ] = arr [ i ]
			i , k = i + 1 , k + 1
		else :
			temp [ k ] = arr [ j ]
			k , j = k + 1 , j + 1
	while ( i <= mid - 1 ) :
		temp [ k ] = arr [ i ]
		i , k = i + 1 , k + 1
	while ( j <= right ) :
		temp [ k ] = arr [ j ]
		j , k = j + 1 , k + 1
	for i in range ( left , right + 1 ) :
		arr [ i ] = temp [ i ]
	return inv_count
arr = [ 1 , 20 , 6 , 4 , 5 ]
n = len ( arr )
print ( mergeSort ( arr , n ) )