mergesort.py

import math


def mergesort(arr, helper=None, low=0, high=None):
    print(arr, helper, low, high)
    if high == None:
        print("Setting high...")
        high = len(arr) - 1
    if helper is None:
        print("Setting helper...")
        helper = list(map(lambda x: None, list(range(len(arr)))))
    if low < high:
        middle = math.floor((low + high) / 2)
        print("Setting Middle: ", low, middle, high)
        mergesort(arr, helper, low, middle)
        mergesort(arr, helper, middle+1, high)
        merge(arr, helper, low, middle, high)
    return arr

def merge(arr, helper, low, middle, high):
    print("Merge: ", low, high, helper, arr)
    for i in range(low, high+1):
        helper[i] = arr[i]
    print("Setting Merge Helper: ", helper, low, middle, high)
    helperLeft = low
    helperRight = middle + 1
    current = low

    # iterate through helper array
    while (helperLeft <= middle and helperRight <= high):
        print("Helper comparison: ", current, helperLeft, middle, helperRight, high)
        if helper[helperLeft] <= helper[helperRight]:
            arr[current] = helper[helperLeft]
            helperLeft += 1
        else:
            arr[current] = helper[helperRight]
            helperRight += 1
        current += 1
    # copy rest of left to target
    remaining = middle - helperLeft
    for i in range(0,remaining+1):
        arr[current + i] = helper[helperLeft + i]
    print("Merged array: ", arr)
    return arr

print(mergesort([4, 3, 2, 1]))