HackerRank Merge Sort: Counting Inversions

I found the description of this problem in its HackerRank page a bit misleading. Better trust its name instead. We have to count the inversions that occur when we run a merge-sort algorithm on list of positive integers.

So, basically, we have to increase a variable to keep track of the inversions and return it to the caller. If you know how to implement merge-sort, large part of the job is done.

The main problem is that they set the timeout very tightly, and it could be tough respecting it, especially if you are using an implementation language that is not among the fastest ones.

I use Python here, so I had to be careful. At least if I don't want to use PyPy to speed everything up.

In the end I came out with this stuff:

def count_inversions(a):
    return merge_sort(a, 0, len(a) - 1)

The required count_inversions() simply calls my adapted merge-sort() function.

Beside sorting, it also stores in the variable result the count of all the inversions, and then will return it.

def merge_sort(a, left, right):
    result = 0
    if left < right:
        center = left + (right - left) // 2
        result += merge_sort(a, left, center)
        result += merge_sort(a, center + 1, right)
        result += merge(a, left, center, right)
    return result

As you see, no surprise, it's a standard merge-sort implementation.

I have spent some sweating on merge, to save to most time I could without getting something still readable:

def merge(data, left, center, right):
def merge(data, left, center, right):
    merged = []  # 1
    result = 0  # 2

    i = left  # 3
    j = center + 1
    while i <= center and j <= right:  # 4
        if data[i] > data[j]:  # 5
            result += (center - i + 1)
            merged.append(data[j])
            j += 1
        else:
            merged.append(data[i])
            i += 1

    for i in range(i, center+1):  # 6
        merged.append(data[i])
    for j in range(j, right+1):
        merged.append(data[j])

    data[left:right+1] = merged  # 7
    return result

1. We need some temporary area where storing the merged data. I use this list.
2. Keep track of the swaps happening here.
3. The main while below runs on two loop variables, i and j, representing the indexes to the left and right elements.
4. Loop until there is at least one element on the left and one on the right to be merged.
5. If an element on the left is bigger than the ones on the right, we have a swap. Or better, as many swaps as the number of elements still on the right.
6. Take care of the leftover.
7. Replace the part of the list on which we worked with the merged elements.

Fast enough to get accepted. Test case and python script on GitHub.