#!/usr/bin/env python2

numlist = [0, 2, 4, 1, -5, 4, 1, 5, 49, 24, 13, -50, 40, -24, 44, 9]

def merge (left, right, cmp_function):
    list = []

    # while either list has elements
    while len(left) > 0 or len(right) > 0:

        # if both lists have elements, do the comparison to see which goes first
        if len(left) > 0 and len(right) > 0:
            if cmp_function(left[0], right[0]):
                list.append(left.pop(0))
            else:
                list.append(right.pop(0))

        # if only one list has elements, push them into the result list
        elif len(left) > 0:
            list.append(left.pop(0))

        elif len(right) > 0:
            list.append(right.pop(0))

    return list

def merge_sort (list, cmp_function):
    length = len(list)

    # if the list has only one element, it's already sorted
    if length == 1:
        return list

    middle = (length + 1) / 2

    # divide list in two, by the middle
    left, right = [list[i:i+middle] for i in range(0, len(list), middle)]

    # merge sort left and right parts
    left = merge_sort(left, cmp_function)
    right = merge_sort(right, cmp_function)

    # merge left and right into one list
    return merge(left, right, cmp_function)

print merge_sort(numlist, lambda a, b: a > b)