def merge(left, right, lt):
    """Assumes left and right are sorted lists.
     lt defines an ordering on the elements of the lists.
     Returns a new sorted(by lt) list containing the same elements
     as (left + right) would contain."""
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if lt(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 sort(L, lt = lambda x,y: x < y):
    """Returns a new sorted list containing the same elements as L"""
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = sort(L[:middle], lt)
        right = sort(L[middle:], lt)
        print 'About to merge', left, 'and', right
        return merge(left, right, lt)

L = [35, 4, 5, 29, 17, 58, 0]
newL = sort(L)
print 'Sorted list =', newL
L = [1.0, 2.25, 24.5, 12.0, 2.0, 23.0, 19.125, 1.0]

newL = sort(L, float.__lt__)
print 'Sorted list =', newL

About to merge [4] and [5]
About to merge [35] and [4, 5]
About to merge [29] and [17]
About to merge [58] and [0]
About to merge [17, 29] and [0, 58]
About to merge [4, 5, 35] and [0, 17, 29, 58]
Sorted list = [0, 4, 5, 17, 29, 35, 58]
About to merge [1.0] and [2.25]
About to merge [24.5] and [12.0]
About to merge [1.0, 2.25] and [12.0, 24.5]
About to merge [2.0] and [23.0]
About to merge [19.125] and [1.0]
About to merge [2.0, 23.0] and [1.0, 19.125]
About to merge [1.0, 2.25, 12.0, 24.5] and [1.0, 2.0, 19.125, 23.0]
Sorted list = [1.0, 1.0, 2.0, 2.25, 12.0, 19.125, 23.0, 24.5]