Which Sorting Algorithm When?

Start with the data, not the algorithm. Ask four questions: is the data already partially ordered, how many elements are there, how much extra memory can you spend, and does the key have a small numeric range? Those four answers rule out most options immediately.

def merge_sort(values):
    if len(values) <= 1:
        return list(values)
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]


data = [5, 2, 9, 1, 7]
print(merge_sort(data))
print(sorted(data))

The outputs agree: 1, 2, 5, 7, 9. The hand-written merge sort splits the array in half, sorts each half and merges them, which is why its cost does not depend on the input order.

The mechanism behind the choices is that every comparison sort needs logarithmically many rounds of comparisons in the worst case, because a comparison can only split the possibilities in two. So all of them sit at O of n log n, and the differences between them are about constants, stability and space. A non-comparison sort such as counting sort breaks that lower bound by exploiting the structure of the keys, which is why it becomes O of n plus k.

The trade-off to name is the choice of failure mode. Merge sort guarantees its bound and needs linear space; quicksort is in place and fast but can degrade to quadratic; heapsort is in place with a guaranteed bound but has poor cache behaviour; counting sort beats the comparison bound but only for small integer keys. In production the honest answer is usually the library sort, because Python's Timsort is stable, adaptive to existing runs, and implemented in C.

The built-in sorted function takes an iterable and returns a new sorted list, and the list method sort does the same thing in place. Neither needs a hand-written algorithm, and both are far faster than anything you would write in Python.

values = [5, 2, 9, 1, 7]
print(sorted(values))
print(sorted(values, reverse=True))

The outputs are 1, 2, 5, 7, 9 and 9, 7, 5, 2, 1. The reverse flag flips the comparison rather than reversing the result, which matters because reversing a sorted list would put the equal elements in the wrong order.

The mechanism is that the built-in sort is Timsort, a hybrid of insertion sort and merge sort. It looks for naturally ascending or descending runs in the input and merges them, which means already sorted or nearly sorted data is handled in close to linear time, while random data still gets the guaranteed O of n log n bound. It also uses Timsort's stability, so equal elements keep their original relative order.

The trade-off to name is that sorted returns a new list and leaves the original untouched, while the sort method rewrites the list in place and returns nothing. Using the wrong one is a common source of confusion, so say which you mean. Beyond speed, the built-in sort gives you stability and adaptivity for free, and it accepts a key function so you can sort by a field without building an intermediate list of tuples yourself.

Counting sort does not compare values at all. It counts how many times each value appears, then walks the possible values in order and emits each one as many times as it was counted.

def counting_sort(values):
    if not values:
        return []
    highest = max(values)
    counts = [0] * (highest + 1)
    for value in values:
        counts[value] += 1
    output = []
    for value, count in enumerate(counts):
        output.extend([value] * count)
    return output


data = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(data))

The output is 1, 2, 2, 3, 3, 4, 8, which is the input in order with the same multiplicities.

The mechanism is that the count array is indexed by value, so the position of each item in the output is determined directly rather than by comparing it against other items. The two passes are a counting pass over the input and an emitting pass over the count array, so the time is O of n plus k, where k is the size of the value range, and the space is O of k.

The trade-off is that this is only a win when k is comparable to n. If the values run from zero to a billion, the count array is a billion cells and the algorithm is worse than useless, while a comparison sort would never allocate anything like that. So counting sort needs small, dense, non-negative integer keys. Radix sort extends the idea to larger keys by processing one digit at a time, and bucket sort generalises it to arbitrary keys with a known distribution. Mentioning that the output preserves multiplicity and that the algorithm is stable by construction is a good detail to add.