Skip to content
Tutorials Center
My learning

Topics

Lesson 84 of 225 ยท Sorting

Counting, Radix and Bucket Sort

Learn non-comparison sorting in Python. Stable counting sort, LSD radix sort and bucket sort beat O(n log n) in the right cases, with traces, code and limits.

Every sort you have met so far (bubble, insertion, merge, quick, heap) works by comparing two elements and asking "which one is bigger?". There is a mathematical limit for such algorithms: any comparison sort needs at least about n log n comparisons in the worst case (see Sorting Basics).

Can we do better? Yes, if we are allowed to look inside the keys. When the keys are small integers, fixed-length strings, or numbers spread evenly over a known range, we can sort without ever comparing two elements to each other. Instead we use the key as an index, a digit, or a bucket number. These algorithms run in time proportional to n (plus the size of the key range), but they only work on certain data. In this lesson you will build three of them from scratch: counting sort, radix sort and bucket sort, and learn exactly when each one wins or fails.

Counting sort

Imagine sorting 20 exam marks that are whole numbers from 0 to 10. Instead of comparing marks, make a tally sheet with 11 boxes, one for each possible mark. Walk through the list once and add a tally mark to the box matching each value. Then read the boxes from 0 to 10 and write each value out as many times as it was tallied.

TEXT
input:  [3, 1, 4, 1, 3, 3, 0]        keys are in range 0..4

count:   index:  0  1  2  3  4
         count:  1  2  0  3  1

output: 0 | 1 1 | (no 2s) | 3 3 3 | 4   ->  [0, 1, 1, 3, 3, 3, 4]
Python Counting sort for small integers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The time is O(n + k), where n is the number of elements and k is the size of the range (max_value + 1). The extra space is O(k) for the tally array plus the output. For exam marks this is excellent; for 20 values between 0 and a billion it would be absurd, because k dwarfs n.

The stable version

The simple version above only works for plain numbers: it re-creates values from counts, so it forgets which original element was which. To sort records by a small integer key (say, people by age) and keep equal keys in their original order, we need the stable version. It turns the counts into prefix sums that tell where each key's block begins in the output, then places the elements one by one.

TEXT
keys:   [2, 0, 2, 1, 0]       range 0..2
count:  [2, 1, 2]
start:  [0, 2, 3]       <- start index of each key's block (prefix sums, shifted by one)

place each element, left to right, at start[key], then start[key] += 1

Placing from left to right with a moving start index keeps equal keys in input order, which makes the sort stable. That property is not a nicety: radix sort below depends on it.

Python Stable counting sort on records

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ana and Cy both have key 2, and Ana still comes first in the output. Bo and Ed (key 0) also keep their order.

Counting sort handles negative numbers or a range that starts above zero by subtracting the minimum: use key(item) - min_value as the index.

When counting sort works and when it does not

The cost is O(n + k). If k is about the same size as n or smaller, counting sort is linear time. If k is much larger than n (for example, sorting 1,000 timestamps), the loop over the range is wasted work. Let us count the steps to see the crossover.

Python When the key range is too large

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a range of 1,000,000, counting sort needs about a hundred times more steps than a comparison sort on the same 1,000 elements. Counting sort is an excellent tool for small, bounded integer keys such as ages, grades, digits, or character codes, and a poor one for anything else.

Radix sort

What if the numbers are large? Radix sort breaks each key into digits and sorts by one digit at a time, using a stable sort (counting sort, with only 10 possible digits) for each pass. The surprising part is the order: in LSD (least significant digit) radix sort, you start with the last digit and finish with the first.

TEXT
input:     170, 45, 75, 90, 802, 24, 2, 66

sort by ones digit:     170 90 802 2 24 45 75 66
sort by tens digit:     802 2 24 45 66 170 75 90
sort by hundreds digit: 2 24 45 66 75 90 170 802   <- sorted

Why does it work? After the pass for a given digit, the list is sorted by the last few digits examined so far. The next pass sorts by a more significant digit; because that pass is stable, numbers with the same current digit stay in the order the earlier passes gave them. By the last pass, ties on the top digit are broken by the lower digits. That is why stability matters: an unstable pass would destroy the work of the earlier passes.

Python LSD radix sort for non-negative integers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the largest number has d digits and each pass costs O(n + b) with b = 10 (the base), the total is O(d ยท (n + b)). For numbers that fit in a fixed number of digits, d is a constant, and radix sort is O(n). Be careful about hiding things in "constant": numbers up to n have about logโ‚โ‚€ n digits, so for n distinct values the cost is O(n log n) again, just with a different base. Radix sort shines when keys are short fixed-width codes: phone numbers, dates in YYYYMMDD form, IP addresses, or fixed-length strings.

The same approach sorts fixed-length strings if you treat each character as a digit:

Python Radix sort on three-letter words

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here sorted(buckets) orders the (few) distinct characters, and appending to a list keeps each bucket in input order, so each pass is stable.

Bucket sort

Bucket sort is designed for real numbers that are spread roughly uniformly over a known interval, for example floats in [0, 1). Split the interval into n equal-width buckets, drop each number into the bucket it belongs to, sort each bucket (they are tiny), and concatenate the buckets in order.

TEXT
values in [0, 1), 5 buckets of width 0.2

bucket 0 [0.0, 0.2):  0.13 0.05
bucket 1 [0.2, 0.4):  0.34 0.21
bucket 2 [0.4, 0.6):  0.42
bucket 3 [0.6, 0.8):  0.77
bucket 4 [0.8, 1.0):  0.91 0.86

sort each bucket, then join:  0.05 0.13 0.21 0.34 0.42 0.77 0.86 0.91
Python Bucket sort for floats in [0, 1)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With n values spread uniformly over n buckets, each bucket holds about one element on average, so sorting all buckets costs O(n) in expectation and the whole sort is O(n) on average. The catch is the assumption. If the data is clustered (say, all values land in one bucket), then that one bucket holds everything and the cost becomes whatever the inner sort costs: O(n log n) with Python's sort, or O(nยฒ) if you used insertion sort inside.

Python Bucket sizes with uniform and clustered data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pigeonhole sort

Pigeonhole sort is the cousin of counting sort for the case where every key is a number in a small range and you want to keep the actual items, not just counts. Make one "hole" for each possible value between min and max, drop every item into its hole (the pigeonhole principle: n items, k holes), then read the holes in order.

Compared with counting sort (above), pigeonhole sort stores the items themselves in the holes, so it can sort records by an integer key directly. It is stable (items are appended in input order) and runs in O(n + k) time and space, where k = max - min + 1. Like counting sort it is only sensible when k is not much bigger than n.

Python Pigeonhole sort on numbers and records

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows the weakness: sorting just two values, 1 and 1,000,000, would allocate a million empty holes. When the range is wide, use radix sort or a comparison sort instead.

Comparing the three

Algorithm Time Extra space Stable Needs
Counting sort O(n + k) O(n + k) Yes (prefix-sum version) integer keys in a small range k
Radix sort (LSD) O(d ยท (n + b)) O(n + b) Yes fixed-width keys with d digits in base b
Bucket sort O(n) average, O(nยฒ) worst O(n) Yes if the inner sort is uniformly distributed values over a known range

Notice that all three need extra memory and extra knowledge about the data, which is the price of beating the comparison bound. The O(n log n) lower bound is not wrong; it simply does not apply to algorithms that do something other than compare.

When to use them (and when not)

  • Sorting millions of small integers such as ages, scores or byte values: counting sort.
  • Sorting fixed-width IDs, phone numbers, dates, or integers of bounded size: radix sort.
  • Sorting floats from a uniform source, such as results of a random generator: bucket sort.
  • Sorting anything general (mixed strings, objects with custom order): use sorted, which is a comparison-based hybrid; see Shell Sort, Timsort and Hybrid Sorts.
  • In Python, the interpreter overhead of these loops often outweighs their asymptotic advantage, so sorted usually wins on speed for ordinary list sizes. They matter in languages with fast loops and in algorithms that use counting as a building block, such as suffix arrays.

Common mistakes

  • Using counting sort when the range is huge. Check k first. If it is far larger than n, use a comparison sort.
  • Radix sort from the most significant digit with the same code. LSD needs the least significant digit first and a stable inner sort.
  • Losing stability. Filling the output array from the right with a decremented index is also stable if you iterate the input backwards; mixing directions breaks it.
  • Negative numbers. Shift the keys by the minimum or sort negatives and positives separately.
  • Floats outside [0, 1). int(v * n) would index out of range. Normalize with (v - low) / (high - low) and guard the maximum value.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the time complexity of counting sort on n integers in the range 0..k-1?

    One pass tallies the n elements and one pass walks through the k counters, so the cost is n + k steps.
  2. 2. Why must each pass of LSD radix sort be stable?

    When two numbers share the current digit, only the earlier passes can tell them apart. A stable pass leaves them in that order.
  3. 3. In which situation is counting sort a poor choice?

    The loop over the key range costs about a billion steps for only 1,000 values, much more than a comparison sort needs.
  4. 4. When does bucket sort degrade to its worst case?

    Uniformly spread input gives tiny buckets. If one bucket receives almost everything, the work is the cost of sorting that single bucket.
  5. 5. Why does counting sort not break the O(n log n) lower bound?

    The lower bound is for algorithms that learn about order only through comparisons. Counting sort uses extra knowledge about the keys instead.

Summary

  • Non-comparison sorts use the structure of the keys instead of comparing pairs, so the n log n comparison bound does not apply.
  • Counting sort tallies keys in a range of size k and runs in O(n + k); with prefix sums it is stable and sorts records.
  • LSD radix sort applies a stable sort to each digit from least to most significant, costing O(d ยท (n + b)).
  • Bucket sort distributes uniformly spread values into buckets and sorts each one; it is O(n) on average but O(nยฒ) or O(n log n) when the data clusters.
  • Pigeonhole sort drops the items themselves into one hole per key value: stable, O(n + k), and only sensible when the range k is small.
  • All of them need extra memory and assumptions about the data; for general data in Python use sorted.

Next: Shell Sort, Timsort and Hybrid Sorts, the sorts that real libraries use.