### CED github logo Jun 4・1 min read

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.

DISCUSS (3) Hi @theghostyced . so I decided to try and solve this on my own and I want to share my insights

my first solution was to write some logic google the question and I came across a solution that didn't satisfy the complexity

``````def getInvCount(arr, n):

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

return inv_count
``````

I then tried to rewrite this using list comprehension, you can see my effort here

``````def getInvCount(arr, n):
return sum([1 if (arr[i] > arr[j]) else 0 for i in range(n) for j in range(i+1,n)])
``````

but this also revealed the answers which you can use to solve this question.

Thanks @areahints but I think the time complexity still remains the same irrespective of the list comprehension.

yes, I mentioned that my list comprehension didn't satisfy the complexity.

consider this solution;

``````def getInvCount(arr,n):
return mergeGetInvCount(arr)

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))
``````

## Output

``````Number of inversions are 5
``````

that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?

Classic DEV Post from Jan 20

## What do you do to practice new programming languages and/or frameworks? A blogging community of over 100,000 software developers Join dev.to  