def merge(left, right):
    """ Merges two sorted lists into one sorted list """
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif len(left) > 0:
            result.append(left.pop(0))
        elif len(right) > 0:
            result.append(right.pop(0))
    return result

def merge_sort(l):
    if len(l) <= 1:
        return l
    middle = len(l)/2
    left = merge_sort(l[:middle])
    right = merge_sort(l[middle:])
    return merge(left, right)

if __name__ == '__main__':
    import random
    test = [random.randint(0, 25) for x in xrange(100)]
    import time
    start = time.time()
    print 'unsorted: ', test
    print 'sorted: ', merge_sort(test)
    end = time.time()
    print 'time: ', end-start, 'ms'
    assert sorted(test) == merge_sort(test)