def merge_and_count(x, y, result, count):
    i, j = 0, 0

    while i < len(x) and j < len(y):
        if x[i] > y[j]:
            result.append(y[j])
            j += 1
            count += 1
        else:
            result.append(x[i])
            i += 1

    result += x[i:]
    result += y[j:]

    return result, count

def sort_and_count(array):
    if len(array) == 1:
        return array, 0

    count = 0
    result = []

    mid = len(array)//2

    x = array[:mid]
    y = array[mid:]

    x, c1 = sort_and_count(x)
    y, c2 = sort_and_count(y)

    result, c3 = merge_and_count(x, y, result, count)

    return result, (c1+c2+c3)

def main():
    array = [1,3,5,2,4,6]
    result, count = sort_and_count(array)
    print("there are", count, "split inversion")
    print(result)