```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ``` ```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 ```
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ``` ```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] ```