Counting and Radix Sort

You have 300 quiz papers, each scored from 0 to 10, and you need them in order. You could merge sort them. Or you could put 11 empty trays on the desk, labelled 0 to 10, drop each paper into the tray for its score, and then stack the trays in order. One look per paper, and no paper is ever compared with another.

That is counting sort. It beats every sort from the earlier lessons, but only because the scores are small whole numbers in a known range.

#The O(n log n) wall

Merge sort, quicksort and heap sort all learn about the order by asking one question: is this item smaller than that one? Sorts that only ask that question can never do better than O(n log n) in the worst case.

Here is why. n items can be arranged in n × (n − 1) × … × 1 different orders, and the sort has to tell them all apart. Each comparison has two answers, so at best it cuts the possible orders in half. Halving that many orders down to one takes about n log₂ n comparisons. For 10 items there are 3,628,800 orders, and halving down to 1 takes at least 22 comparisons.

Counting sort steps around this wall: it never compares two items, and uses each key as an array index instead.

#The idea: count, then place

Say every key is a whole number from 0 to k − 1.

1. Count how many items have each key.
2. Work out where each key starts in the output. Keys of 0 start at position 0. Keys of 1 start right after all the 0s, keys of 2 right after all the 0s and 1s, and so on. That is a running total of the counts, a prefix sum.
3. Place each item, in input order, at its key's start position, and move that start position one step forward.

Step 3 walks the input from front to back, so items with equal keys land in the order they came in. So counting sort is stable, which radix sort will need.

In the trace below, the keys are 0 to 3, and the letter tells equal keys apart: 3a and 3b both have key 3, and 3a came first.

for each item: count[key] += 1start[0] = 0for v from 1 to k - 1: start[v] = start[v - 1] + count[v - 1]for each item, in input order:  out[start[key]] = item  start[key] += 1

The code takes a key function that turns an item into its whole-number key, so it can sort records, not only bare numbers. Radix sort reuses it below.

// key(item) must be a whole number from 0 to k - 1
function countingSortBy(items, key, k) {
  const count = new Array(k).fill(0);
  for (const item of items) count[key(item)]++;
  const start = new Array(k).fill(0); // start[v] = items with key < v
  for (let v = 1; v < k; v++) start[v] = start[v - 1] + count[v - 1];
  const out = new Array(items.length);
  for (const item of items) {
    out[start[key(item)]++] = item; // input order: stable
  }
  return out;
}
 
countingSortBy([3, 1, 3, 0, 2, 1], (x) => x, 4); // [0, 1, 1, 2, 3, 3]

# key(item) must be a whole number from 0 to k - 1
def counting_sort_by(items, key, k):
    count = [0] * k
    for item in items:
        count[key(item)] += 1
    start = [0] * k  # start[v] = items with key < v
    for v in range(1, k):
        start[v] = start[v - 1] + count[v - 1]
    out = [None] * len(items)
    for item in items:  # input order: stable
        out[start[key(item)]] = item
        start[key(item)] += 1
    return out
 
counting_sort_by([3, 1, 3, 0, 2, 1], lambda x: x, 4)  # [0, 1, 1, 2, 3, 3]

#Radix sort: one digit at a time

Counting sort needs one counter per possible key. For quiz scores that is 11 counters. For order numbers up to a billion, it would be a billion counters, which is hopeless.

Radix sort fixes that by sorting on one digit at a time. Each digit is 0 to 9, so each pass is a counting sort with just 10 counters. The surprising part is the order: start with the last digit (the ones), then the tens, then the hundreds.

Here is why it works. The last pass decides by the most important digit. When two numbers tie on that digit, stability leaves them in the order the earlier passes chose, and that order was already correct for the lower digits. Each pass keeps all the work of the passes before it.

// non-negative integers; uses countingSortBy from above
function radixSort(nums) {
  const biggest = nums.reduce((m, x) => Math.max(m, x), 0);
  for (let place = 1; place <= biggest; place *= 10) {
    nums = countingSortBy(nums, (x) => Math.floor(x / place) % 10, 10);
  }
  return nums;
}
 
radixSort([512, 38, 407, 223, 95, 340, 18]);
// [18, 38, 95, 223, 340, 407, 512]

# non-negative integers; uses counting_sort_by from above
def radix_sort(nums):
    biggest = max(nums, default=0)
    place = 1
    while place <= biggest:
        nums = counting_sort_by(nums, lambda x: x // place % 10, 10)
        place *= 10
    return nums
 
radix_sort([512, 38, 407, 223, 95, 340, 18])
# [18, 38, 95, 223, 340, 407, 512]

#Every sort in this module

Here n is the number of items, k the number of possible keys, d the number of digits and b the base.

Best cases assume distinct keys. With all keys equal, heap sort takes O(n) and the quicksort from its lesson takes O(n²).

In real code, call the built-in sort unless the right-hand column gives you a reason not to.

#Common mistakes

#Check yourself

#What to practise next

Sorting is often a first step. Once data is sorted, you can find anything in it in O(log n) with Binary Search, the next lesson.