DCP44 - Out of order arrays

'''
This problem was asked by Google.
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.
Given an array, count the number of inversions it has. Do this faster than O(N^2) 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, 2), and (4, 3).
The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.
'''

def countInversions(ARRAY):
    # I will use bubblesort method
    array = ARRAY.copy()
    counter = 0
    inversions = list()
    for i in range(len(array)-1):
        for j in  range(i+1, len(array)):
            if array[i] > array[j]:
                array[i], array[j] = array[j], array[i]
                counter += 1
                inversions.append(str(array[i]) + "-" + str(array[j]))
    return counter, inversions

# MAIN FUNCTION
array1 = [2, 4, 1, 3, 5]
counter1, inversions1 = countInversions(array1)
print(str(array1) + " ----> " + str(counter1) + " inversions #### " + str(inversions1))
array2 = [5, 4, 3, 2, 1]
counter2, inversions2 = countInversions(array2)
print(str(array2) + " ----> " + str(counter2) + " inversions #### " + str(inversions2))