I couldn’t find any working Python 3.3 mergesort algorithm codes, so I made one myself. Is there any way to speed it up? It sorts 20,000 numbers in about 0.3-0.5 seconds
def msort(x): result = [] if len(x) < 2: return x mid = int(len(x)/2) y = msort(x[:mid]) z = msort(x[mid:]) while (len(y) > 0) or (len(z) > 0): if len(y) > 0 and len(z) > 0: if y[0] > z[0]: result.append(z[0]) z.pop(0) else: result.append(y[0]) y.pop(0) elif len(z) > 0: for i in z: result.append(i) z.pop(0) else: for i in y: result.append(i) y.pop(0) return result
Advertisement
Answer
You can initialise the whole result list in the top level call to mergesort:
result = [0]*len(x) # replace 0 with a suitable default element if necessary. # or just copy x (result = x[:])
Then for the recursive calls you can use a helper function to which you pass not sublists, but indices into x
. And the bottom level calls read their values from x
and write into result
directly.
That way you can avoid all that pop
ing and append
ing which should improve performance.