algorithms course - assignment 1

mergesort.py

array = open("integerarray.txt")
number_list = array.read()
number_list = number_list.strip()
number_list = [int(i) for i in number_list.split('\n')]

def mergesort(splits, array):
    array_length = len(array)
    if array_length > 1:
        middle = array_length//2
        left_side = array[:middle]
        right_side = array[middle:]

        ls, left_side = mergesort(0, left_side)
        rs, right_side = mergesort(0, right_side)

        output = []
        i, j = 0, 0
        upper = array_length - middle

        while i < middle and j < upper:
            if left_side[i] < right_side[j]:
                output.append(left_side[i])
                i += 1
            else:
                output.append(right_side[j])
                splits += (middle - i)
                j += 1

        while i < middle:
            output.append(left_side[i])
            i += 1

        while j < upper:
            output.append(right_side[j])
            j += 1

        array = output
        splits = splits + ls + rs

    return splits, array

mergesort(0, number_list)