27 lines
669 B
Python
27 lines
669 B
Python
def mergesort(xs):
|
|
if len(xs) < 2: return xs
|
|
|
|
leng = len(xs) // 2
|
|
left = mergesort(xs[:leng])
|
|
right = mergesort(xs[leng:])
|
|
|
|
# Reversing is O(n), but so is copying, so
|
|
# this does not worsen complexity.
|
|
# It does slow us down, but... oh well :)
|
|
left.reverse()
|
|
right.reverse()
|
|
|
|
# Since we're reversed, the smallest numbers
|
|
# are on the end. We can thus use pop (O(1))
|
|
total = []
|
|
while left != [] and right != []:
|
|
if left[-1] <= right[-1]:
|
|
total.append(left.pop())
|
|
else:
|
|
total.append(right.pop())
|
|
|
|
left.reverse()
|
|
right.reverse()
|
|
total += left + right
|
|
return total
|