How Radix Sort Works
Sort by least significant digit, then next digit, repeat. Non-comparison sort that runs in O(d times n) rather than O(n log n).
What you will learn
- Why radix sort skips comparisons entirely and what that costs in terms of domain restrictions
- How the RADIX constant controls both the bucket count and the digit-extraction formula
- How the placement variable moves through digit positions from ones to tens to hundreds
- Why the bucket-gather loop restores the stable relative order of elements with matching digits
- How the four doctests cover duplicates, forward and reverse ranges, and mixed magnitudes
- Why radix sort is faster than comparison sorts on bounded-key integer inputs
Prerequisites
- Comfort reading Python integer arithmetic and list comprehensions
- No prior knowledge of radix sort or bucket sort required
The story behind radix sort
Radix sort predates electronic computers. Herman Hollerith's tabulating machines, built for the 1890 United States Census, sorted punched cards by mechanically reading one column at a time and routing each card into a physical bin numbered 0 through 9. Processing all cards by the least significant digit, then re-running the deck by the next digit, and so on produced a fully sorted deck after as many passes as there were columns. That is LSD (least-significant-digit) radix sort, and it is the variant in this file.
The theoretical importance of radix sort is that it breaks the O(n log n) lower bound that applies to comparison sorts. Because it never compares two elements against each other, it is not constrained by the decision-tree argument that limits merge sort and quicksort. Instead, its runtime is O(d times (n + k)) where d is the number of digit positions, n is the element count, and k is the base (10 in this file). On inputs where d is small and k is fixed, this is effectively O(n).
The practical catch is domain restriction: radix sort only works on non-negative integers in this implementation. Floating-point numbers, negative integers, and strings each require a variant or a transformation. Production radix sort implementations such as those inside database sort-merge joins handle those cases but are significantly more complex than this 42-line file.
Module Docstring and the RADIX Constant
sorts/radix_sort.py:1A one-sentence docstring and a Wikipedia source link. The RADIX constant pins base 10 and is the only tunable parameter in the file.
Two decisions are visible before the first function. Line 4 links the implementation directly to its Wikipedia source, which the contribution checklist requires for algorithms that have an authoritative external reference. Line 7 imports __future__.annotations, which defers evaluation of type hints so forward-reference strings in annotations are not resolved at import time; at the pinned Python 3.14 this is largely redundant but the import signals intent. Line 9 declares RADIX = 10 as a module-level constant in UPPER_CASE per the PEP 8 convention for constants. Every bucket allocation, digit-extraction formula, and loop range in the file references RADIX rather than the literal 10. Changing RADIX to 2 or 16 would pivot the implementation to binary or hexadecimal radix sort with no other edits required.
The RADIX constant drives every bucket count and digit formula. Changing it to 2 or 16 gives binary or hexadecimal radix sort without any other code changes.
"""
This is a pure Python implementation of the radix sort algorithm
Source: https://en.wikipedia.org/wiki/Radix_sort
"""
from __future__ import annotations
RADIX = 10Signature and the Four Doctests
sorts/radix_sort.py:12The function takes a list of non-negative integers. Four doctests cover duplicates, a forward range, a reverse range, and mixed magnitudes.
The docstring omits the usual :param and :return: lines and goes straight to examples. That brevity is acceptable under the contribution checklist when the function name and type hint are self-explanatory. The four doctests are more carefully chosen than they appear. The duplicate test on line 15 verifies stability indirectly: two 2s stay adjacent in the output even though they passed through multiple digit-position rounds. The forward-range test on line 18 checks that 0 through 14 sorts correctly after three digit positions. The reverse-range test on line 20 checks the same range presented in the hardest possible order. The magnitude test on line 22 forces the outer loop to reach four digit positions (1, 10, 100, 1000) and confirms that shorter numbers survive the extra passes without being corrupted.
The magnitude doctest forces four digit-position passes and pins that shorter numbers like 1 and 10 survive them undamaged.
def radix_sort(list_of_ints: list[int]) -> list[int]:
"""
Examples:
>>> radix_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> radix_sort(list(range(15))) == sorted(range(15))
True
>>> radix_sort(list(range(14,-1,-1))) == sorted(range(15))
True
>>> radix_sort([1,100,10,1000]) == sorted([1,100,10,1000])
True
"""
placement = 1
max_digit = max(list_of_ints)Placement and the Outer Loop
sorts/radix_sort.py:25placement starts at 1 (ones digit) and multiplies by RADIX each pass. The loop exits when placement exceeds the maximum element.
Line 26 calls max(list_of_ints) once before the loop to bound the number of passes. A list whose maximum is 999 needs three passes (ones, tens, hundreds); a list whose maximum is 1 needs one. The outer while condition placement <= max_digit exits as soon as placement exceeds the largest element, which means no element could contribute a non-zero digit at that position. Line 29 creates ten empty bucket lists at the start of each pass. The buckets are recreated every iteration rather than cleared, which keeps the code readable at the cost of list allocation overhead. Line 41 multiplies placement by RADIX, advancing from ones to tens to hundreds. The return on line 42 returns the same list modified in place.
max(list_of_ints) bounds the pass count. placement multiplies by RADIX each round to advance through digit positions from ones upward.
placement = 1
max_digit = max(list_of_ints)
while placement <= max_digit:
# declare and initialize empty buckets
buckets: list[list] = [[] for _ in range(RADIX)]
# split list_of_ints between the buckets
for i in list_of_ints:
tmp = int((i / placement) % RADIX)
buckets[tmp].append(i)
# put each buckets' contents into list_of_ints
a = 0
for b in range(RADIX):
for i in buckets[b]:
list_of_ints[a] = i
a += 1
# move to next
placement *= RADIX
return list_of_intsDigit Extraction and Bucket Assignment
sorts/radix_sort.py:31Dividing by placement and taking modulo RADIX isolates the current digit. Each element goes into the bucket matching that digit.
Line 32 is the entire digit-extraction logic. Dividing i by placement shifts the digit of interest into the ones position: at placement=1, dividing 345 gives 345.0; at placement=10, it gives 34.5; at placement=100, it gives 3.45. Taking % RADIX after that division gives the remainder mod 10, which is the ones digit of the shifted value: 345 mod 10 is 5, 34.5 mod 10 is 4.5 (truncates to 4), and 3.45 mod 10 is 3.45 (truncates to 3). That three-step formula extracts the ones, tens, and hundreds digits on successive passes. The int() call converts the float result to an integer index for buckets[]. Each element is appended to its bucket, preserving relative order among elements sharing a digit at this position.
int((i / placement) % RADIX) shifts right with division and isolates the digit with modulo. The int() converts the float to a bucket index.
for i in list_of_ints:
tmp = int((i / placement) % RADIX)
buckets[tmp].append(i)Bucket Gather and Why Radix Sort Is Stable
sorts/radix_sort.py:34The gather loop reads buckets 0 through 9 in order, writing elements back. Equal-digit elements keep their relative order from the previous pass.
The gather phase reads buckets 0 through 9 in ascending order and writes their contents back into list_of_ints at consecutive positions starting from 0. The counter a on line 36 advances once per element written. Because bucket 0 is read before bucket 1, and so on, elements with a smaller digit at this position appear earlier in the output than elements with a larger digit. Within each bucket, elements appear in the order they were appended during the scatter phase, which is their order in list_of_ints at the start of this pass. That preserved append order is what makes LSD radix sort stable: elements that are equal at the current digit position keep their relative order from the previous pass, and the accumulated ordering from all previous passes carries forward into the final result.
Reading buckets in order 0-9 and preserving append order within each bucket is what makes LSD radix sort stable. Earlier digit-position orderings carry through to the final result.
# put each buckets' contents into list_of_ints
a = 0
for b in range(RADIX):
for i in buckets[b]:
list_of_ints[a] = i
a += 1You've walked through 5 key areas of the The Algorithms - Python codebase.
Continue: How Counting Sort Works → Browse all projectsCreate code tours for your project
Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.
Install Intraview Free