[HackerRank][Python3] Merge Sort: Counting Inversions

Problem :

https://www.hackerrank.com/challenges/ctci-merge-sort/problem

My Solution :

#!/usr/bin/env python3


def countInversions(arr, left, right):
    count = 0
    if right - left < 2:
        return count
    middle = (right + left) // 2
    left_count = countInversions(arr, left, middle)
    right_count = countInversions(arr, middle, right)
    count += left_count + right_count
    merged = []
    i, j = left, middle
    while i < middle and j < right:
        if arr[i] > arr[j]:
            merged.append(arr[j])
            j += 1
            count += middle - i
        else:
            merged.append(arr[i])
            i += 1
    if i == middle:
        merged += arr[j:right]
    else:
        merged += arr[i:middle]
    arr[left:right] = merged
    return count


t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().rstrip().split()))
    result = countInversions(arr, 0, n)
    print(result)