#Count Inversions
#Counts the number of inversions in a list.  Inverions defined as occurence of list[i] > list[j] for all combinations of i,j where i<j 
# uses python3

#NOTE:  ONLY MINIMAL TESTING DONE AT THIS POINT
#todo: test more lists

import logging as log

def merge_count(list0, list1):
    log.info("Merging ", list0, list1)
    count = 0
    merged = []
    while list0 and list1:
        if list0[0] <= list1[0]:
            merged.append(list0.pop(0))
        else:
            merged.append(list1.pop(0))
            count += len(list0)
    merged += list0
    merged += list1
    log.info("Result:  ", merged, " counted ", count, " inversions")
    return(merged, count)

def Count_Inversions(inv_list, inversions = 0):
    log.info("Processing ", inv_list, " with inv count ", inversions)
    #base case
    length = len(inv_list)
    if length <= 1:
        log.info("hit bottom with list ", inv_list, " inv count ", inversions)
        return (inv_list,0)
    #recursive case
    index = int(length/2)
    list0 = inv_list[:index]
    list1 = inv_list[index:]
    log.info("Splitting ", inv_list, " into ", list0, " and ", list1)

    left = Count_Inversions(list0)
    right = Count_Inversions(list1)
    #mc = merge_count(list0, list1)
    merged = merge_count(left[0],right[0])
    return (merged[0], left[1] + right[1] + merged[1])