def merge_sort(unsorted_list):
    """Assume unsorted_list is a list, final order depends on compare in merge function.
       Returns a new list with same elements as unsorted_list. """

    if len(unsorted_list) <= 1:
        return unsorted_list

    # Find the middle point and devide it
    middle = len(unsorted_list) // 2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)

    return list(merge(left_list, right_list))

# Merge the sorted halves

def merge(left_half,right_half):
    """Assumes left and right are sorted lists. Final order depends on the compare
       in the if statement.
       Returns a new sorted list containing the same elements as (left + right)."""

    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])

    if len(left_half) == 0:
        res = res + right_half
    else:
        res = res + left_half

    return res

merge([1,3,5], [2,6,8])

[1, 2, 3, 5, 6, 8]

unsorted_list = [64, 34, 25, 12, 22, 11, 90]
unsorted_list

[64, 34, 25, 12, 22, 11, 90]

%%time
merge_sort(unsorted_list)

CPU times: user 11 µs, sys: 4 µs, total: 15 µs
Wall time: 16.7 µs

[11, 12, 22, 25, 34, 64, 90]

# Same merge sort algorithm, but now with the compare passed as an argument.

def merge_2(left, right, compare):
    """Assumes left and right are sorted lists and compare defines an ordering on the elements.
       Returns a new sorted list containing the same elements as (left + right)."""

    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while (i < len(left)):
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result

def merge_sort_2(L, compare = lambda x, y: x < y):
    """Assumes L is a list, compare defines an ordering of elements of L.
       Returns a new sorted list with same elements as unsorted_list. """

    if len(L) < 2:
        return L[:]

    # Find the middle point, divide, and sort
    else:
        middle = len(L) // 2
        left = merge_sort_2(L[:middle], compare)
        right = merge_sort_2(L[middle:], compare)

        return merge_2(left, right, compare)

merge_2([2,4,6,8], [1,3,5,7], lambda x, y: x < y)

[1, 2, 3, 4, 5, 6, 7, 8]

unsorted_list = [64, 34, 25, 12, 22, 11, 12, 9, 30, 90]
merge_sort_2(unsorted_list)

[9, 11, 12, 12, 22, 25, 30, 34, 64, 90]

%time
merge_sort_2(unsorted_list, lambda x, y: x > y)

CPU times: user 2 µs, sys: 0 ns, total: 2 µs
Wall time: 4.29 µs

[90, 64, 34, 30, 25, 22, 12, 12, 11, 9]