radix sort

Radix sort is a non-comparison sorting algorithm that orders keys by processing them one digit position at a time, distributing items into buckets on each pass instead of comparing them against one another.

A key is the value an item gets sorted by, and it works as long as it splits into positions drawn from a fixed alphabet, such as decimal digits, bytes, or characters. The radix is the size of that alphabet, so base-10 integers need ten buckets and raw bytes need 256. Each pass sends every item to the bucket matching its digit at the current position, then collects the buckets back in order.

Least significant digit (LSD) radix sort starts at the rightmost position and works leftward. It is correct only when each pass uses a stable inner sort, meaning items with the same digit keep their existing order. That’s why counting sort is the usual inner step. Preserving the order earlier passes established is what leaves the sequence sorted at the end.

Step through a full LSD run below, one digit position at a time, and watch the buckets fill and empty until the list comes out sorted.

Interactive diagram — enable JavaScript to view.

Most significant digit (MSD) radix sort instead starts at the leftmost position and recursively sorts each bucket. That order suits variable-length keys such as strings, where lexicographic order turns on the earliest differing character.

The cost of either variant hinges on key length rather than on comparisons:

  • Time: O(d(n + b)) for n items, d digit positions, and a radix of b, which is linear in n whenever d and b stay small.
  • Space: O(n + b) auxiliary room for the buckets and the output, so radix sort doesn’t sort in place.
  • Stability: LSD radix sort keeps equal keys in their original relative order, inheriting the stability of its inner sort.

The method predates the stored-program computer. Herman Hollerith’s tabulating machines sorted punched cards column by column from 1887, and Harold H. Seward adapted it to computer memory at MIT in 1954. It still suits fixed-width integer and string keys, though Python’s own Timsort is comparison-based.

Sorting Algorithms in Python

Tutorial

Sorting Algorithms in Python

In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.

intermediate algorithms python

For additional information on related topics, take a look at the following resources:

Have a question about this? Mentor AI can show you examples, compare related terms, and point you to tutorials.

  • Ask Mentor AI
  • Pick a question and Mentor AI takes it from here.
By Martin Breuss • Updated Oct. 6, 2026
Computer Science Glossary Share Feedback