Count inversions

In computer science, an inversion in an array occurs when two elements at different indices in the array are in the opposite order. For example, in the array [1, 3, 2], the elements 3 and 2 form an inversion.

You can count the number of inversions in an array in O(n log n) time complexity using themerge_sort algorithm. The basic idea is to count the number of inversions recursively in the left and right halves of the array, and then count the number of inversions between the left and right halves during the merge step.

# function to count inversions in an array using merge sort
def count_inversions(arr):
    if len(arr) <= 1:
        return 0
    
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # recursively count inversions in left and right halves
    count_left = count_inversions(left)
    count_right = count_inversions(right)
    
    # count inversions between left and right halves during merge step
    i = j = k = count = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
            count += len(left) - i
        k += 1
    
    # copy remaining elements from left or right halves
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1
    
    # return total number of inversions
    return count_left + count_right + count
 
# example usage
arr = [2, 4, 1, 3, 5]
count = count_inversions(arr)
print(count)  # output: 3