given an arraylike data structure a1 n how many pairs i j for all 1 i j n such that ai aj these pairs are called inversions counting the number of such inversions in an arraylike object is the important among other things counting inversions can help us determine how close a given array is to being sorted in this implementation i provide two algorithms a divideandconquer algorithm which runs in nlogn and the bruteforce n2 algorithm counts the number of inversions using a naive bruteforce algorithm parameters arr arr arraylike the list containing the items for which the number of inversions is desired the elements of arr must be comparable returns numinversions the total number of inversions in arr examples countinversionsbf1 4 2 4 1 4 countinversionsbf1 1 2 4 4 0 countinversionsbf 0 counts the number of inversions using a divideandconquer algorithm parameters arr arraylike the list containing the items for which the number of inversions is desired the elements of arr must be comparable returns c a sorted copy of arr numinversions int the total number of inversions in arr examples countinversionsrecursive1 4 2 4 1 1 1 2 4 4 4 countinversionsrecursive1 1 2 4 4 1 1 2 4 4 0 countinversionsrecursive 0 counts the inversions across two sorted arrays and combine the two arrays into one sorted array for all 1 ilenp and for all 1 j lenq if pi qj then i j is a cross inversion parameters p arraylike sorted in nondecreasing order q arraylike sorted in nondecreasing order returns r arraylike a sorted array of the elements of p and q numinversion int the number of inversions across p and q examples countcrossinversions1 2 3 0 2 5 0 1 2 2 3 5 4 countcrossinversions1 2 3 3 4 5 1 2 3 3 4 5 0 if p1 qj then pk qk for all i k lenp these are all inversions the claim emerges from the property that p is sorted this arr has 8 inversions 10 2 10 1 10 5 10 5 10 2 2 1 5 2 5 2 testing an array with zero inversion a sorted arr1 an empty list should also have zero inversions counts the number of inversions using a naive brute force algorithm parameters arr arr array like the list containing the items for which the number of inversions is desired the elements of arr must be comparable returns num_inversions the total number of inversions in arr examples count_inversions_bf 1 4 2 4 1 4 count_inversions_bf 1 1 2 4 4 0 count_inversions_bf 0 counts the number of inversions using a divide and conquer algorithm parameters arr array like the list containing the items for which the number of inversions is desired the elements of arr must be comparable returns c a sorted copy of arr num_inversions int the total number of inversions in arr examples count_inversions_recursive 1 4 2 4 1 1 1 2 4 4 4 count_inversions_recursive 1 1 2 4 4 1 1 2 4 4 0 count_inversions_recursive 0 counts the inversions across two sorted arrays and combine the two arrays into one sorted array for all 1 i len p and for all 1 j len q if p i q j then i j is a cross inversion parameters p array like sorted in non decreasing order q array like sorted in non decreasing order returns r array like a sorted array of the elements of p and q num_inversion int the number of inversions across p and q examples _count_cross_inversions 1 2 3 0 2 5 0 1 2 2 3 5 4 _count_cross_inversions 1 2 3 3 4 5 1 2 3 3 4 5 0 if p 1 q j then p k q k for all i k len p these are all inversions the claim emerges from the property that p is sorted this arr has 8 inversions 10 2 10 1 10 5 10 5 10 2 2 1 5 2 5 2 testing an array with zero inversion a sorted arr_1 an empty list should also have zero inversions
def count_inversions_bf(arr):
    

    num_inversions = 0
    n = len(arr)

    for i in range(n - 1):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                num_inversions += 1

    return num_inversions


def count_inversions_recursive(arr):
    
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    p = arr[0:mid]
    q = arr[mid:]

    a, inversion_p = count_inversions_recursive(p)
    b, inversions_q = count_inversions_recursive(q)
    c, cross_inversions = _count_cross_inversions(a, b)

    num_inversions = inversion_p + inversions_q + cross_inversions
    return c, num_inversions


def _count_cross_inversions(p, q):
    

    r = []
    i = j = num_inversion = 0
    while i < len(p) and j < len(q):
        if p[i] > q[j]:
            
            
            
            num_inversion += len(p) - i
            r.append(q[j])
            j += 1
        else:
            r.append(p[i])
            i += 1

    if i < len(p):
        r.extend(p[i:])
    else:
        r.extend(q[j:])

    return r, num_inversion


def main():
    arr_1 = [10, 2, 1, 5, 5, 2, 11]

    
    

    num_inversions_bf = count_inversions_bf(arr_1)
    _, num_inversions_recursive = count_inversions_recursive(arr_1)

    assert num_inversions_bf == num_inversions_recursive == 8

    print("number of inversions = ", num_inversions_bf)

    

    arr_1.sort()
    num_inversions_bf = count_inversions_bf(arr_1)
    _, num_inversions_recursive = count_inversions_recursive(arr_1)

    assert num_inversions_bf == num_inversions_recursive == 0
    print("number of inversions = ", num_inversions_bf)

    
    arr_1 = []
    num_inversions_bf = count_inversions_bf(arr_1)
    _, num_inversions_recursive = count_inversions_recursive(arr_1)

    assert num_inversions_bf == num_inversions_recursive == 0
    print("number of inversions = ", num_inversions_bf)


if __name__ == "__main__":
    main()