Counting Sort & Timsort

Merge sort and quick sort compare items two at a time. It can be proved that any sort that only compares items needs about n log n comparisons in the worst case. But if the items are small whole numbers, you can avoid comparisons completely and sort in linear time. That is what counting sort does.

In this lesson you will write counting sort and radix sort, then look inside Python's own sorted(), which uses an adaptive algorithm called Timsort, and learn to use it like a professional. At the end, a table compares every sort in this course.

Counting sort

Suppose 1,20,000 students took an exam marked out of 100, and you need the marks in order. There are only 101 possible values. Instead of comparing marks, count how many students got each mark, then write each mark out as many times as it was counted.

def counting_sort(values, max_value):
    counts = [0] * (max_value + 1)
    for v in values:
        counts[v] += 1                     # one pass to count
    result = []
    for value, how_many in enumerate(counts):
        result.extend([value] * how_many)  # one pass over the counts
    return result

marks = [67, 45, 98, 45, 72, 100, 0, 67, 88, 45]
print(counting_sort(marks, 100))

[0, 45, 45, 45, 67, 67, 72, 88, 98, 100]

The time is O(n + k), where n is the number of items and k is the range of values (here 101). For a lakh of exam marks that is far faster than O(n log n). The catch: it only works for whole numbers (or things you can turn into them) in a small range. Sorting ten numbers between 0 and 1,00,00,000 would waste memory on a crore of counters.

Stable counting sort for records

Usually you sort records, not bare numbers: students by marks, orders by priority. The trick is to turn the counts into starting positions with a prefix sum (see Arrays & Dynamic Arrays), then place each record in its slot. Walking through the input in order keeps the sort stable.

def counting_sort_by(records, key, max_key):
    counts = [0] * (max_key + 1)
    for r in records:
        counts[key(r)] += 1
    starts = [0] * (max_key + 1)           # where each key's block begins
    for k in range(1, max_key + 1):
        starts[k] = starts[k - 1] + counts[k - 1]
    output = [None] * len(records)
    for r in records:                      # input order: stable
        output[starts[key(r)]] = r
        starts[key(r)] += 1
    return output

orders = [("Pizza", 2), ("Medicine", 0), ("Groceries", 1),
          ("Insulin", 0), ("Books", 2), ("Milk", 1)]
for name, priority in counting_sort_by(orders, key=lambda r: r[1], max_key=2):
    print(priority, name)

0 Medicine
0 Insulin
1 Groceries
1 Milk
2 Pizza
2 Books

Medicine came before Insulin in the input, and it still does. Stability is what makes the next algorithm work.

Radix sort

Radix sort sorts numbers with many digits by running a stable counting sort once per digit, starting with the last digit. Each pass only has 10 possible keys (0 to 9). Because every pass is stable, the order from earlier digits is kept when later digits tie.

def radix_sort(numbers, digits):
    for d in range(digits):                         # ones, tens, hundreds...
        buckets = [[] for _ in range(10)]
        for n in numbers:
            buckets[(n // 10 ** d) % 10].append(n)  # stable: keeps order
        numbers = [n for b in buckets for n in b]
        print(f"after digit {d + 1}: {numbers}")
    return numbers

pin_codes = [411001, 124001, 302017, 682011, 226010, 110001]
radix_sort(pin_codes, 6)

after digit 1: [226010, 411001, 124001, 682011, 110001, 302017]
after digit 2: [411001, 124001, 110001, 226010, 682011, 302017]
after digit 3: [411001, 124001, 110001, 226010, 682011, 302017]
after digit 4: [110001, 411001, 682011, 302017, 124001, 226010]
after digit 5: [302017, 110001, 411001, 124001, 226010, 682011]
after digit 6: [110001, 124001, 226010, 302017, 411001, 682011]

With d digits, radix sort is O(d × (n + 10)), linear in n for fixed-length keys such as PIN codes, phone numbers or roll numbers.

Timsort: how Python sorts

sorted() and list.sort() use Timsort, designed by Tim Peters for Python in 2002. Its key insight is that real data is rarely random: it often contains runs, stretches that are already in order. Timsort works in three steps:

1. Scan the list and find natural runs. A strictly descending run is reversed in place.
2. Extend short runs to a minimum length (between 32 and 64 items) using binary insertion sort, which is fast on small pieces.
3. Merge the runs, like merge sort, using a "galloping" mode that skips ahead quickly when one run keeps winning.

Since Python 3.11, the rule that decides which runs to merge next comes from an algorithm called Powersort, but the overall design is still Timsort. You can see how adaptive it is by counting the comparisons it makes on 1,000 items arranged in different ways:

import random

class Counted:
    comparisons = 0
    def __init__(self, value):
        self.value = value
    def __lt__(self, other):              # sorted() only uses <
        Counted.comparisons += 1
        return self.value < other.value

def count_sort_comparisons(values):
    Counted.comparisons = 0
    sorted(Counted(v) for v in values)
    return Counted.comparisons

random.seed(5)
n = 1000
nearly = list(range(n))
for _ in range(10):
    i, j = random.randrange(n), random.randrange(n)
    nearly[i], nearly[j] = nearly[j], nearly[i]
cases = {
    "already sorted": list(range(n)),
    "reversed": list(range(n, 0, -1)),
    "10 random swaps": nearly,
    "two sorted halves": list(range(0, n, 2)) + list(range(1, n, 2)),
    "fully random": random.sample(range(n), n),
}
for name, data in cases.items():
    print(f"{name:>18}: {count_sort_comparisons(data):>5} comparisons")

   already sorted:   999 comparisons
         reversed:   999 comparisons
  10 random swaps:  2745 comparisons
two sorted halves:  1999 comparisons
     fully random:  8682 comparisons

Sorted and reversed lists need just n - 1 comparisons, O(n): one run is found and, if descending, reversed. Two sorted halves cost one scan plus one merge. Only fully random data needs the full O(n log n). Timsort is also stable, and its worst case is O(n log n).

Using sorted() well

You will rarely write a sort in real code, but you will use sorted() every day. Three habits make it powerful:

from operator import itemgetter

players = [("Rohan", "Delhi", 412), ("Kabir", "Delhi", 530),
           ("Isha", "Pune", 530), ("Meera", "Kochi", 388)]

# 1. key= picks what to compare
print(sorted(players, key=itemgetter(2), reverse=True))

# 2. A tuple key sorts by several fields: runs high to low, then name A to Z
print(sorted(players, key=lambda p: (-p[2], p[0])))

# 3. Stability: sort by the minor key first, then the major key
by_name = sorted(players, key=itemgetter(0))
by_city = sorted(by_name, key=itemgetter(1))
print([f"{p[1]}:{p[0]}" for p in by_city])

[('Kabir', 'Delhi', 530), ('Isha', 'Pune', 530), ('Rohan', 'Delhi', 412), ('Meera', 'Kochi', 388)]
[('Isha', 'Pune', 530), ('Kabir', 'Delhi', 530), ('Rohan', 'Delhi', 412), ('Meera', 'Kochi', 388)]
['Delhi:Kabir', 'Delhi:Rohan', 'Kochi:Meera', 'Pune:Isha']

In the first result Kabir stays ahead of Isha because he came first in the input; the tuple key in the second breaks the tie by name instead. The key function is called once per item, not once per comparison, so even an expensive key is cheap. The negative sign in -p[2] reverses only the runs, which works for numbers; for strings, use the two-pass stable method shown third.

All the sorts compared

Heap sort is explained in Heaps & Priority Queues, because it needs the heap data structure.

Common mistakes

• Counting sort on a huge range. The count array needs one slot per possible value; use it only when k is small.
• Starting radix sort from the first digit with a simple stable pass. Least significant digit first is the version that works.
• Writing your own sort in production code. sorted() is faster, stable and well tested.
• Using cmp-style functions. Python 3 sorts take key=; if you have an old two-argument compare function, wrap it with functools.cmp_to_key().

Key points

• Comparison sorts need about n log n comparisons in the worst case; counting sort avoids comparisons.
• Counting sort runs in O(n + k) for whole numbers in a small range k, and can be made stable with prefix sums.
• Radix sort applies a stable counting sort digit by digit, starting from the last digit.
• Python's Timsort finds natural runs, uses insertion sort on short runs and merges them; it is stable and O(n) on sorted data.
• Use key=, tuple keys and stability to sort records by several fields.

ages = [12, 14, 13, 12, 15, 14, 14, 13, 12, 16, 15, 13, 14, 12, 16]
LOW, HIGH = 10, 18

counts = [0] * (HIGH - LOW + 1)
for a in ages:
    counts[a - LOW] += 1

result = []
for i, c in enumerate(counts):
    result.extend([i + LOW] * c)
print(result)

for i, c in enumerate(counts):
    if c:
        print(f"age {i + LOW}: {c}")

[12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 15, 15, 16, 16]
age 12: 4
age 13: 3
age 14: 4
age 15: 2
age 16: 2