Fast sorting

The fast sorts use divide and conquer: split the problem into smaller pieces, solve those, and combine the answers.

Merge sort splits the list in half, sorts each half (by splitting again, down to single items, which are already sorted), then merges the two sorted halves. Merging is quick: look at the front of each half and take the smaller, over and over.

def merge_sort(xs):
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    left, right = merge_sort(xs[:mid]), merge_sort(xs[mid:])
    out = []
    while left and right:
        out.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
    return out + left + right

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

There are about log₂ n levels of halving, and each level does about n steps of merging, so merge sort is O(n log n) every time. For a million items that's about 20 million steps instead of a trillion. Its cost is the extra memory for the merged lists.

Quicksort picks one item as the pivot, moves smaller items to its left and bigger ones to its right, then sorts each side the same way. It's usually the fastest in practice and needs little extra memory, but a bad pivot every time (say, always the first item of an already-sorted list) makes it O(n²). Picking the pivot at random avoids that.

No sort that works by comparing items can beat O(n log n) in general. Python's own sorted() uses Timsort, a merge sort that also spots runs that are already in order.