Solutions for counting the number of inversions

    • @JavierVow
    • @jacob, submitted in Python 3, achived 100% score
    def merge(a_with_inv, b_with_inv):
        i, k = 0, 0
        merged = list()
        a, a_inv = a_with_inv
        b, b_inv = b_with_inv
        inversions = a_inv + b_inv
    
        while i < len(a) and k < len(b):
            if a[i] < b[k]:
                merged.append(a[i])
                i += 1
            else:
                merged.append(b[k])
                inversions += len(a[i:])
                k += 1
    
        while i < len(a):
            merged.append(a[i])
            i += 1
        while k < len(b):
            merged.append(b[k])
            k += 1
    
        return merged, inversions
    
    
    def merge_sort(arr):
        if not arr or len(arr) == 1:
            return arr, 0
    
        mid = len(arr) // 2
        merged_array, inversions = merge(
            merge_sort(arr[:mid]), merge_sort(arr[mid:]))
    
        return merged_array, inversions
    
    
    def solve(arr):
        _, inversions = merge_sort(arr)
        return inversions