[Algorithm question by Google] solve for O(nlogn) #python3 #big-o

algoGoogle.md

QUESTION

We can determine how "out of order" an array A is by counting the number of inversions it has.

Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.

CHALLENGE

Given an array, count the number of inversions it has. Do this faster than O(N2) time.

You may assume each element in the array is distinct.

For example, a sorted list has zero inversions. The array [2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1), and (4, 3). The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.

Link

algoGoogle.py

def getInvCount(arr,n):
    return mergeGetInvCount(arr)[1]

def mergeGetInvCount(arr):
    if len(arr) <= 1:
        return arr, 0
    middle = int(len(arr) / 2)
    left, a = mergeGetInvCount(arr[:middle])
    right, b = mergeGetInvCount(arr[middle:])
    result, c = mergeGetSplitInvCount(left, right)
    return result, (a + b + c)

def mergeGetSplitInvCount(left, right):
    result = []
    count = 0
    i,j = 0,0
    left_len = len(left)
    while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += left_len - i
            j += 1
    result += left[i:]
    result += right[j:]
    return result, count   

# Driver Code
arr = [1, 20, 6, 4, 5] 
n = len(arr) 
print("Number of inversions are", getInvCount(arr,n))