Count Inversions in an array with Python 2.7

count_inversions_io.py

import timeit


def get_table():
    table = []
    with open("IntegerArray.txt", 'r') as f:
        for line in f:
            table.append(int(line))
    return table


def merge_list(left, right):
    result = list()
    i, j = 0, 0
    inv_count = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        elif right[j] < left[i]:
            result.append(right[j])
            j += 1
            inv_count += (len(left)-i)
    result += left[i:]
    result += right[j:]
    return result, inv_count


def test_sort_and_count():
    sort_and_count(get_table())


def sort_and_count(array):
    if len(array) < 2:
        return array, 0
    middle = len(array) / 2
    left, inv_left = sort_and_count(array[:middle])
    right, inv_right = sort_and_count(array[middle:])
    merged, count = merge_list(left, right)
    count += (inv_left + inv_right)
    return merged, count


def test_bit_count():
    bit_count(get_table())


def bit_count(a, m=(1 << 64)):
    if not m or not a:
        return 0
    count = 0
    ones, zeros = [], []
    for n in a:
        if n & m:
            ones.append(n & ~m)
        else:
            count += len(ones)
            zeros.append(n & ~m)
    m /= 2
    return count + bit_count(ones, m) + bit_count(zeros, m)


if __name__ == '__main__':
    # data from: http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt
    # just place it in the same working directory
    print 'Non-comparative sorting algorithm: ' +\
        str(timeit.timeit(stmt="test_bit_count()",
                          setup="from __main__ import test_bit_count",
                          number=2))  # should take around 7-10s
    print 'Divide-and-conquer: ' +\
        str(timeit.timeit(stmt="test_sort_and_count()",
                          setup="from __main__ import test_sort_and_count",
                          number=2))  # should take around 3s

    print bit_count(get_table())  # O(n w)
    merge_lis, inv = sort_and_count(get_table())
    print inv  # O(n logn)