Python,
pasted
on Feb 23:

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

Output:

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]

