Sorting Algorithm

Radix Sort

Sorts integers digit by digit — ones first, then tens, then hundreds — using a stable pass at each position. Because it never directly compares two full numbers, it can sort fixed-width integers faster than any comparison sort, given enough of them.

BestO(nk)
AverageO(nk)
WorstO(nk)
SpaceO(n + b)
StableYes

Try It — Animated Flow

29
8
44
15
3
37
21
Radix sort sorts numbers digit by digit, least significant first, using a stable pass at each digit.
Step 1 / 6
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Phone numbers & account IDs
Fixed-width identifiers (phone numbers, national IDs, invoice numbers) are a perfect fit — radix sort processes millions of them digit-by-digit, faster than comparing them as whole numbers.
IP address sorting
IPv4 addresses are just 32-bit integers; network tools sort huge address tables using radix-style byte-at-a-time passes.
Suffix array construction
Building suffix arrays for string-matching algorithms (used in search engines and bioinformatics) relies on radix sort to rank fixed-length substrings quickly.
Its literal origin: punch-card sorters
Radix sort predates computers — early 20th-century mechanical card-sorting machines sorted punched cards column by column, which is exactly this algorithm.

Trade-offs

Reach for it when
  • You're sorting fixed-width integers (or fixed-length strings)
  • The number of digits k is small relative to n
  • You need a stable sort without comparisons
Avoid it when
  • You're sorting arbitrary objects with custom comparators
  • Keys have wildly varying or unbounded length
  • Memory for auxiliary buckets is tight