public
Created

Merge sort benches

  • Download Gist
mergebench.py
Python
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
import timeit
 
def badmergeSort(array):
if len(array) <= 1:
return array
else:
left = array[:len(array)/2]
right = array[len(array)/2:]
return badmerge(badmergeSort(left),badmergeSort(right))
 
def badmerge(array1,array2):
merged_array=[]
while len(array1) > 0 or len(array2) > 0:
 
if array2 and not array1:
merged_array.append(array2.pop(0))
 
elif (array1 and not array2) or array1[0] < array2[0]:
merged_array.append(array1.pop(0))
 
else:
merged_array.append(array2.pop(0))
return merged_array
 
def nolenmerge(array1,array2):
merged_array=[]
while array1 or array2:
if not array1:
merged_array.append(array2.pop(0))
elif (not array2) or array1[0] < array2[0]:
merged_array.append(array1.pop(0))
else:
merged_array.append(array2.pop(0))
return merged_array
 
def nolenmergeSort(array):
n = len(array)
if n <= 1:
return array
left = array[:n/2]
right = array[n/2:]
return nolenmerge(nolenmergeSort(left),nolenmergeSort(right))
 
assert nolenmergeSort([9,8,7,6,5,4,3,2,1]) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
def fastmerge(array1,array2):
merged_array=[]
while array1 or array2:
if not array1:
merged_array.append(array2.pop())
elif (not array2) or array1[-1] > array2[-1]:
merged_array.append(array1.pop())
else:
merged_array.append(array2.pop())
merged_array.reverse()
return merged_array
 
def fastmergeSort(array):
n = len(array)
if n <= 1:
return array
left = array[:n/2]
right = array[n/2:]
return fastmerge(fastmergeSort(left),fastmergeSort(right))
 
assert fastmergeSort([9,8,7,6,5,4,3,2,1]) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
# Alone, this will run out of recursion depth because Python does not do TCO,
# for lists of length > 100
 
def cps_merge_sort(array):
return cpsmergeSort(array,lambda x:x)
 
def cpsmergeSort(array,continuation):
n = len(array)
if n <= 1:
return continuation(array)
left = array[:n/2]
right = array[n/2:]
return cpsmergeSort (left, lambda leftR:
cpsmergeSort(right, lambda rightR:
continuation(fastmerge(leftR,rightR))))
 
assert cps_merge_sort([9,8,7,6,5,4,3,2,1]) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
# This is trampoline-based tco elimination (not very efficient)
 
thunk = lambda name, *args: lambda: name(*args)
 
def trampoline(bouncer):
while callable(bouncer):
bouncer = bouncer()
return bouncer
 
def tco_cpsmergeSort(array,continuation):
n = len(array)
if n <= 1:
return continuation(array)
left = array[:n/2]
right = array[n/2:]
return thunk (tco_cpsmergeSort, left, lambda leftR:
thunk (tco_cpsmergeSort, right, lambda rightR:
(continuation(fastmerge(leftR,rightR)))))
 
mycpomergesort = lambda l: trampoline(tco_cpsmergeSort(l,lambda x:x))
 
assert mycpomergesort([9,8,7,6,5,4,3,2,1]) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
# That's not a problem ! We can do TCO ourselves !
 
def tcomergeSort(array):
sortedstuff,tosort = [],[array]
while tosort:
array = tosort.pop()
n = len(array)
if n > 1: # this is a normal call, recurse
tosort.append(array[n/2:])
tosort.append(array[:n/2])
else:# we're returning : integrate the nodes to the sorted stuff
while sortedstuff:
leftR = sortedstuff.pop()
array = fastmerge(leftR,array)
sortedstuff.append(array)
return sortedstuff[0]
 
assert tcomergeSort([9,8,7,6,5,4,3,2,1]) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
def leftcomb(l):
maxn,leftcomb = len(l),[]
n = maxn/2
while maxn > 1:
leftcomb.append((l[n:maxn],False))
maxn,n = n,n/2
return l[:maxn],leftcomb
 
def tcomergesort(l):
l,stack = leftcomb(l)
while stack: # l sorted, stack contains tagged slices
i,ordered = stack.pop()
if ordered:
l = fastmerge(l,i)
else:
stack.append((l,True)) # store return call
rsub,ssub = leftcomb(i)
stack.extend(ssub) #recurse
l = rsub
return l
 
assert tcomergesort([9,8,7,6,5,4,3,2,1]) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
def bubble_sort (l):
swapped = True
while swapped:
swapped = False
for i in xrange(len(l)-1):
if l[i] > l[i+1]:
l[i],l[i+1] = l[i+1],l[i]
swapped = True
 
# Python's native timsort
code = 'import random; l = random.sample(xrange(10000000), 10000); l.sort()'
t = timeit.Timer(code)
print "Python's native (Tim)sort time:",t.timeit(100) / 100
# The slow bubble sort (don't have the patience to test on more than 1)
code = 'import random; l = random.sample(xrange(10000000), 10000); bubble_sort(l)'
t = timeit.Timer(code,'from __main__ import bubble_sort')
print "Bubblesort time:",t.timeit(1) / 1
# badmerge sort
code = 'import random; l = random.sample(xrange(10000000), 10000); badmergeSort(l)'
t = timeit.Timer(code,'from __main__ import badmergeSort')
print "Original Mergesort time:",t.timeit(100) / 100
# merge sort
code = 'import random; l = random.sample(xrange(10000000), 10000); nolenmergeSort(l)'
t = timeit.Timer(code,'from __main__ import nolenmergeSort')
print "no-len Mergesort time:",t.timeit(100) / 100
# fast merge sort
code = 'import random; l = random.sample(xrange(10000000), 10000); fastmergeSort(l)'
t = timeit.Timer(code,'from __main__ import fastmergeSort')
print "no-len Mergesort + fastmerge time:",t.timeit(100) / 100
# trampolined tail-recursive fast merge sort
code = 'import random; l = random.sample(xrange(10000000), 10000); mycpomergesort(l)'
t = timeit.Timer(code,'from __main__ import mycpomergesort')
print "trampolined mergesort + fastmerge time:",t.timeit(100) / 100
# manually tail-call-eliminated fast merge sort
code = 'import random; l = random.sample(xrange(10000000), 10000); tcomergesort(l)'
t = timeit.Timer(code,'from __main__ import tcomergesort')
print "Manual tail-call-optimized mergesort + fastmerge time:",t.timeit(100) / 100

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.