9 def merge(xs, start, divide, end):
11 while start < divide and xs[start] < xs[divide]:
20 # if start < divide is implied by the most recent check
21 while divide < end and xs[divide - 1] < xs[end - 1]:
27 swap(xs, start, divide)
33 while i < divide and j < end:
42 #merge(xs, start, i, divide)
43 #merge(xs, divide, j, end)
44 #merge(xs, start, divide, end)
47 #merge(xs, start, i, divide)
48 #merge(xs, start, divide, j)
49 #merge(xs, start, j, end)
52 #merge(xs, i, divide, j)
53 #merge(xs, start, i, j)
54 #merge(xs, start, j, end)
57 #merge(xs, i, divide, j)
59 #merge(xs, start, i, end)
62 merge(xs, divide, j, end)
63 merge(xs, i, divide, end)
64 merge(xs, start, i, end)
69 for i in range(len(xs) - 1):
71 divisions.append(i + 1)
73 divisions.append(len(xs))
75 while len(divisions) > 2:
76 new_divisions = divisions[:]
78 for i in range(1,len(divisions) - 1,2):
79 merge(xs, divisions[i - 1], divisions[i], divisions[i + 1])
80 new_divisions.remove(divisions[i])
82 divisions = new_divisions
84 xs = [i for i in range(1000)]
94 print('Swaps:', swap.counter)
96 def group_swap(xs, start, divide, end):
97 if start == divide or divide == end:
100 width = divide - start
101 for i in range(start, end):
102 swap(xs, i, i + width if i + width < end else start + i + width - end)