Complexity

Time complexity alone does not pick a sorting algorithm. You also need the gap between best, average and worst case, extra memory, stability, and sensitivity to input patterns. This chapter tabulates the main sorts, shows why comparison sorting cannot beat n log n, and explains how counting and radix sort sidestep that bound.

Comparison table

Here k is the value range, d the number of digits and b the base (values per digit). Quicksort's O(log n) stack holds only when the implementation recurses on the smaller side; naive recursion on both sides can go O(n) deep.

Analyzing merge sort and quicksort

Merge sort follows the recurrence T(n) = 2T(n/2) + O(n). Halving gives log n levels, each level merges n elements in total, so the cost is O(n log n). The split ignores the data, so best and worst case are the same.

Quicksort depends on how evenly the pivot splits the array. Even splits give O(n log n); if one side is always empty, the cost is n + (n - 1) + ... + 1 = O(n²). With a random pivot the expected number of comparisons is about 1.39 n log₂ n, a bit more than merge sort, but quicksort scans contiguous memory in place and is usually faster in practice. You can measure how badly a naive "first element as pivot" quicksort does on sorted input:

import random

def quicksort_count(a, choose):
    comparisons = 0
    stack = [(0, len(a) - 1)]
    while stack:
        lo, hi = stack.pop()
        if lo >= hi:
            continue
        p = choose(lo, hi)
        a[p], a[hi] = a[hi], a[p]
        pivot, i = a[hi], lo
        for j in range(lo, hi):
            comparisons += 1
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        stack += [(lo, i - 1), (i + 1, hi)]
    return comparisons

n = 2000
print(quicksort_count(list(range(n)), lambda lo, hi: lo))               # 1999000 = n(n-1)/2
print(quicksort_count(list(range(n)), lambda lo, hi: random.randint(lo, hi)))  # roughly 25000

The Ω(n log n) lower bound

A comparison sort learns the order only through yes/no questions of the form "is a < b?". Drawing every possible sequence of questions gives a decision tree whose leaves correspond to permutations of the input. There are n! orderings of n distinct elements, so the tree needs at least n! leaves, and a binary tree of height h has at most 2^h leaves. Hence 2^h ≥ n!, so h ≥ log₂(n!). Since n! is at least (n/2)^(n/2), we get log₂(n!) ≥ (n/2) log₂(n/2), and the worst-case number of comparisons is Ω(n log n).

This means merge sort and heapsort are asymptotically optimal. It also means that dropping the "comparisons only" assumption can buy speed.

import math

for n in [10, 100, 1000]:
    lower = math.ceil(math.log2(math.factorial(n)))
    print(n, lower, round(n * math.log2(n)))
# 10 22 33
# 100 525 664
# 1000 8530 9966

Sorting without comparisons

Counting sort runs in O(n + k) when the value range k is comparable to n or smaller. Ages, scores from 0 to 100 and byte values are good fits; when k is huge, time and memory follow k.

Radix sort splits w-bit integers into r-bit digits and runs d = w / r stable counting passes. For 32-bit integers with 8-bit digits, d = 4 and b = 256, so the cost is 4(n + 256), effectively linear. Fixed-length strings can be sorted the same way.

def radix_sort(a, bits=32, r=8):
    mask = (1 << r) - 1
    for shift in range(0, bits, r):
        buckets = [[] for _ in range(1 << r)]
        for x in a:                      # appended in order, so each pass is stable
            buckets[(x >> shift) & mask].append(x)
        a = [x for bucket in buckets for x in bucket]
    return a

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

This version handles non-negative integers only; negatives need the sign bit flipped or a separate pass.

Summary

• Merge sort and heapsort are O(n log n) in the worst case; quicksort is fast on average but needs a good pivot strategy to avoid O(n²).
• The decision-tree argument proves no comparison sort beats Ω(n log n).
• Counting and radix sort exploit integer structure to approach linear time, paying in range limits and memory.
• Real choices also weigh stability, extra memory and adaptivity to nearly sorted input.