Count Inversions + Mergesort

mergesort.py

'''
Gabriel C. 2015

Counting inversions in an array
using merge sort with an auxiliary array
'''

def count_inversions_and_sort(array):
    if len(array) == 1:
        return 0;

    first_half = array[:len(array)/2]
    second_half = array[len(array)/2:]
    inversions = count_inversions_and_sort(first_half)
    inversions += count_inversions_and_sort(second_half)

    i = 0
    j = 0
    for k in xrange(len(array)):
        if i < len(first_half) and j < len(second_half):
            if first_half[i] <= second_half[j]:
                array[k] = first_half[i]
                i += 1
            else:
                array[k] = second_half[j]
                j += 1

                inversions += len(first_half) - i
        else:
            if i < len(first_half):
                array[k] = first_half[i]
                i += 1
            else:
                array[k] = second_half[j]
                j += 1

                inversions += len(first_half) - i

    return inversions;

assert(count_inversions_and_sort([1,3,5,2,4,6]) == 3)
assert(count_inversions_and_sort([1,5,3,2,4]) == 4)
assert(count_inversions_and_sort([5,4,3,2,1]) == 10)
assert(count_inversions_and_sort([1,6,3,2,4,5]) == 5)
assert(count_inversions_and_sort([9,12,3,1,6,8,2,5,14,13,11,7,10,4,0])==56)
assert(count_inversions_and_sort([37,7,2,14,35,47,10,24,44,17,34,11,16,48,1,39,6,33,43,26,40,4,28,5,38,41,42,12,13,21,29,18,3,19,0,32,46,27,31,25,15,36,20,8,9,49,22,23,30,45])==590)
assert(count_inversions_and_sort([4,80,70,23,9,60,68,27,66,78,12,40,52,53,44,8,49,28,18,46,21,39,51,7,87,99,69,62,84,6,79,67,14,98,83,0,96,5,82,10,26,48,3,2,15,92,11,55,63,97,43,45,81,42,95,20,25,74,24,72,91,35,86,19,75,58,71,47,76,59,64,93,17,50,56,94,90,89,32,37,34,65,1,73,41,36,57,77,30,22,13,29,38,16,88,61,31,85,33,54])==2372)
assert(count_inversions_and_sort(range(1,21))==0)
reverse = range(1,11)
reverse.reverse()
assert(count_inversions_and_sort(reverse)==45)
assert(count_inversions_and_sort([1,5,3,4,2,6])==5)
assert(count_inversions_and_sort([6,2,3,4,5,1])==9)
assert(count_inversions_and_sort([9,12,3,1,6,8,2,5,14,13,11,7,10,4,0])==56)