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