Sorting: what Python does, and when to sort yourself

def merge_sort(xs):                    # O(n log n) time, O(n) space
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    left, right = merge_sort(xs[:mid]), merge_sort(xs[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

def counting_sort(xs, max_val):        # O(n + k) for small integers
    counts = [0] * (max_val + 1)
    for x in xs:
        counts[x] += 1
    return [v for v, c in enumerate(counts) for _ in range(c)]

print(merge_sort([1999, 747, 3498, 796, 1348]))
print(counting_sort([3, 1, 2, 3, 0, 2, 1], 3))

[747, 796, 1348, 1999, 3498]
[0, 1, 1, 2, 2, 3, 3]

from functools import cmp_to_key

def largest_number(nums):
    strs = [str(n) for n in nums]
    def order(a, b):                    # which pair reads bigger?
        return -1 if a + b > b + a else (1 if a + b < b + a else 0)
    strs.sort(key=cmp_to_key(order))
    out = "".join(strs)
    return "0" if out[0] == "0" else out

print(largest_number([3, 30, 34, 5, 9]), largest_number([0, 0]))

9534330 0