Counting sort and sorting without comparing in Python

Why this lesson matters

Every sort in the last lesson decides the order by comparing two values. Bubble, selection and insertion sort compare, and merge sort and quick sort compare too. Those comparisons are the only way they learn anything about the values.

There is a proven limit for that style. If a sort learns only by comparing two values at a time, it needs at least about n times log n comparisons in the worst case, where log n is the number of times you can halve n before you reach 1. You do not need the proof yet. The practical meaning is simple: a comparison sort cannot beat n log n in the worst case, no matter how clever it is.

Counting sort gets around that limit by not comparing at all. It looks at the values and counts how many times each one appears. When the values are whole numbers in a small known range, this lets it sort in time that grows with n plus the size of the range, which is O(n + k). The notation O(n + k) is read as "the work is the number of items plus the number of possible values." If the range is small, that is close to a straight line, which is why it is called linear time.

You will use this idea far beyond sorting. Counting letters to check whether two words are anagrams (words that use the same letters in a different order), building a histogram of exam marks, and finding duplicates in a list of ids all use the same counting step.

The idea, with an everyday example

Imagine a teacher who must sort the marks of 1000 students. Each mark is a whole number from 0 to 10. Sorting 1000 papers by comparing pairs would take a long time. A faster method is to make 11 tally boxes, labelled 0 to 10, on the desk.

Walk along the pile of papers once. For each paper, read its mark and put a tick in the box with that label. When the pile is done, every box holds the number of students with that mark. Then read the boxes from 0 to 10 and write down each mark as many times as its box says. The list is sorted, and no two students were ever compared with each other.

That is the whole method. In Python, the tally boxes are a list called count, where count[v] holds how many times the value v appears. The list index is the value, so the box for value 7 is count[7]. A list of 11 zeros is written [0] * 11. The * repeats the list, so [0] * 11 is eleven zeros in a row.

The method has one hard requirement. It needs the values to be whole numbers you can use as an index, and the range must be small enough to make all the boxes. Exam marks from 0 to 10 are ideal. Ages from 0 to 120 are fine. Arbitrary whole numbers that can be billions apart are not, because the boxes would need billions of entries.

Draw the tally boxes for the list 4, 2, 2, 8, 3, 3, 1 on paper. Label nine boxes 0 to 8, and write the count inside each one. Box 2 should hold 2, and box 0 should hold 0.

Let k be the size of the range, which is the biggest value plus one, when the smallest value is 0. For marks from 0 to 10, k is 11. For five numbers where one of them is 2,000,000,000, k is 2,000,000,001 and the method is useless.

The simplest version, step by step

Here is the plain version for non-negative integers. It changes the list in place, like the sorts in the last lesson, and returns nothing.

def counting_sort(a):
    biggest = max(a)                     # find the biggest value
    count = [0] * (biggest + 1)          # one box for every value from 0 to biggest
    for v in a:
        count[v] += 1                    # tally: one tick per value
    idx = 0
    for value in range(biggest + 1):
        for _ in range(count[value]):
            a[idx] = value               # write each value as many times as it was counted
            idx += 1

The loop for v in a is the Python way to visit every item in a list, from the first to the last. You do not need an index. Python hands you one value per turn. You will use this form often.

The name _ in for _ in range(count[value]) means "I do not need this number." It is a convention, not a special rule. The loop runs count[value] times, and the body does not use the loop number.

Trace the function on [4, 2, 2, 8, 3, 3, 1]. There are seven values, and the biggest is 8, so biggest is 8 and the list count has nine boxes, indexes 0 to 8.

• Find the maximum. biggest becomes 8.
• Make the boxes. count is [0, 0, 0, 0, 0, 0, 0, 0, 0], all zero.
• Tally. Read 4: count[4] becomes 1. Read 2: count[2] becomes 1. Read the next 2: count[2] becomes 2. Read 8: count[8] becomes 1. Read 3: count[3] becomes 1. Read the next 3: count[3] becomes 2. Read 1: count[1] becomes 1.

The boxes now read: index 1 holds 1, index 2 holds 2, index 3 holds 2, index 4 holds 1, index 8 holds 1, and every other box holds 0.

• Write back. Start with value = 0. Its box holds 0, so nothing is written. value = 1 holds 1, so write 1 once. value = 2 holds 2, so write 2 twice. value = 3 holds 2, so write 3 twice. value = 4 holds 1, so write 4 once. Values 5, 6 and 7 hold 0, so nothing is written. value = 8 holds 1, so write 8 once.

The list now reads [1, 2, 2, 3, 3, 4, 8]. Counting the writes gives seven, which equals the number of input values. Every value was written exactly as many times as it was read.

The running time has two parts. The max() call and the tally loop each touch every input value once, which is n steps. The write-back loop visits every box, which is k steps, and writes each value once, which is another n steps in total. So the total is O(n + k). The extra memory is the count list, which is O(k).

The next program is the complete version of this method, with a histogram of marks. A histogram is a count per value. The program has the marks built in, so you can run it without typing input.

The output is:

0 appears 1 time(s)
45 appears 3 time(s)
60 appears 1 time(s)
72 appears 2 time(s)
91 appears 1 time(s)
100 appears 1 time(s)
[0, 45, 45, 45, 60, 72, 72, 91, 100]

Look at the histogram lines first. They are the tally in human form. The value 45 appears three times, so the count is 3. The value 2 never appears in the input, so it has no line. Then look at the sorted list. It has nine values, the same as the input, with each value written as many times as it appeared.

The fixed size 101 comes from the rule that marks are from 0 to 100. A program that knows its range can make the list once with that size, and it does not need to search for the maximum first.

Shifting the range for negative values

The simple version breaks on negative values, and Python does not stop it. A negative index in Python counts from the end of the list, as the first lesson showed. So count[-3] reads a real box, just the wrong one. The next program runs the simple version on a list with negative numbers:

The output is:

[0, 3, 3, 5, 5, 5]

The input had six values, and the output has six values, but the -3 values are gone and two 3s appeared. No error was raised. This is the most dangerous kind of bug, because the program finishes and prints a list that looks like a sort. The fix is to shift every value by the smallest value, so the smallest value becomes index 0.

If the smallest value is -3, then -3 becomes 0, -1 becomes 2, and 5 becomes 8. The boxes now cover the range from the minimum to the maximum. The number of boxes is highest - lowest + 1, which is the true size of the range. The next program does exactly that:

The output is:

[-3, -3, -1, 0, 5, 5]

Trace the shift. The minimum is -3 and the maximum is 5, so the range has 5 - (-3) + 1 = 9 boxes. The value -3 goes into box 0, the value -1 into box 2, the value 0 into box 3 and the value 5 into box 8. Two values sit in box 0 (the two -3s) and two sit in box 8 (the two 5s). Write-back adds the minimum back to the box number, so box 0 becomes -3 again. The method works for any range, including ranges that start far below zero, as long as the range itself is small.

The method still needs the list to have at least one value, because min(a) on an empty list raises an error. The common mistakes section shows the message.

Stability: keeping ties in order

The programs so far sort plain numbers. When two plain numbers are equal, you cannot tell them apart, so the order of equal values does not matter. Real data is usually different. You sort students by mark, but each student has a name. Two students with the same mark should keep the order in which they were listed. A sort that does this is stable, as explained in the last lesson.

The simple version above is not stable, because it does not track which item is which. The stable version works with positions. It produces a list of original indexes, sorted by key. This needs one extra idea: the prefix sum. A prefix sum is a running total. After the prefix step, count[v] holds the number of items whose key is v or smaller. That number is the position just after the last item with key v.

Here is the stable method. It returns the order of the original indexes, and the caller uses that order to print the records.

def stable_counting_order(keys, biggest):
    count = [0] * (biggest + 1)
    for k in keys:
        count[k] += 1                        # tally the keys
    for i in range(1, biggest + 1):
        count[i] += count[i - 1]             # prefix sum: count[v] is how many keys are <= v
    order = [0] * len(keys)
    for i in reversed(range(len(keys))):     # go backwards through the input
        count[keys[i]] -= 1                  # move to the slot before the end of the block
        order[count[keys[i]]] = i            # place the item in that slot
    return order

The line reversed(range(len(keys))) walks the indexes from the last one to the first. The function reversed also works on a list directly, as in reversed(a).

Walk through the stable version on five students. Their marks are 72, 91, 72, 60, 91 for Asha, Ravi, Meera, Dev and Kiran, in that order, so the original indexes are 0 to 4.

• Tally. count[60] is 1, count[72] is 2, count[91] is 2, and every other box is 0.
• Prefix sums. count[60] stays 1, because only one key is 60 or less. count[72] becomes 3 (1 + 2), because three keys are 72 or less. count[91] becomes 5 (3 + 2), because all five keys are 91 or less.
• Place from the back. Start at i = 4, the key 91 (Kiran). count[91] drops from 5 to 4, and order[4] gets 4. Then i = 3, the key 60 (Dev). count[60] drops from 1 to 0, and order[0] gets 3. Then i = 2, the key 72 (Meera). count[72] drops from 3 to 2, and order[2] gets 2. Then i = 1, the key 91 (Ravi). count[91] drops from 4 to 3, and order[3] gets 1. Then i = 0, the key 72 (Asha). count[72] drops from 2 to 1, and order[1] gets 0.

The final order is [3, 0, 2, 1, 4]. Reading the names in that order gives Dev, Asha, Meera, Ravi, Kiran. The two 72s keep their input order (Asha before Meera), and the two 91s keep theirs (Ravi before Kiran).

The next program is a complete version that reads names and marks. The data is built in, so you can run it without typing input.

The output is:

Dev 60
Asha 72
Meera 72
Ravi 91
Kiran 91

Compare the output with the trace. The order matches the trace, and the ties are in input order. The sorting is done on the keys, but the program prints the names through the order list, so each name stays with its own mark.

Why does going backwards matter? Think about the two 72s. Asha comes first in the input, Meera second. The backwards loop meets Meera first, places her at the end of the 72 block, and then places Asha one spot earlier. So Asha ends up first, which is the input order. If you went forwards, Asha would be placed at the end of the block first, and Meera would end up before her. The debugging section shows that exact bug.

Python has a shorter tool for this case. sorted() with a key function is stable, and it handles any values, not only small whole numbers. Use counting sort when you want to study the method or when the keys are small whole numbers and speed matters. Use sorted() in ordinary code.

Counting letters

A letter is a character, and every character has a number behind it. Python gives that number with ord(). The character "a" has the number 97, "b" has 98, and "z" has 122. The numbers are consecutive, so ord("b") - ord("a") is 1 and ord("z") - ord("a") is 25. That means you can use a letter as an index, after subtracting ord("a"). A list of 26 boxes covers all lowercase English letters. The function chr() goes the other way, from a number back to a character.

This is counting sort used for something other than sorting. The program below counts the letters in a word and prints the ones that appear, in alphabetical order. The word is built in.

The output is:

a: 3
b: 1
n: 2

Trace one letter. The first a in banana has the value ord("a") - ord("a"), which is 0, so freq[0] becomes 1. The b gives index 1. The first n gives index 13, which is ord("n") - ord("a"). Over the whole word, index 0 ends at 3, index 1 at 1, and index 13 at 2. The loop at the end reads the boxes in order, so the output is alphabetical with no sort at all.

Python also has collections.Counter, which does the tally for you. Counter("banana") gives the same counts in a dictionary (a table that maps each key to a value). The list version above is worth learning because the method is the point. It also runs without the extra import, and it is the form you will use when the keys are small numbers instead of text.

Two anagrams have the same letter counts. The words listen and silent give identical freq lists, which is a fast way to check the anagram rule. You will use that in later problems on strings.

The function chr(ord("a") + i) turns the number back into a letter. Without chr, Python would print the number, such as 97 instead of a. The parentheses matter: ord("a") + i is added first as numbers, then chr turns the result into a character.

Radix sort: counting one digit at a time

Counting sort works on a small range. Some numbers have a big range but a short form. Three-digit numbers have only 1000 possible values, but each one has three digits, and each digit has only ten possible values. Radix sort uses this. It sorts all the numbers by one digit at a time, using a stable counting sort for each digit. The digit positions are handled from the least important to the most important. This form is called LSD radix sort, where LSD means least significant digit first.

Here is the classic example, sorted in three passes on the digits 329, 457, 657, 839, 436, 720, 355.

Input:                 329  457  657  839  436  720  355
 
Pass 1, ones digit:    720  355  436  457  657  329  839
                       (0)  (5)  (6)  (7)  (7)  (9)  (9)
 
Pass 2, tens digit:    720  329  436  839  355  457  657
                       (2)  (2)  (3)  (3)  (5)  (5)  (5)
 
Pass 3, hundreds:      329  355  436  457  657  720  839
                       (3)  (3)  (4)  (4)  (6)  (7)  (8)

Each pass is a stable counting sort on one digit. Stability is what makes the passes work together. In pass 2, the two numbers with tens digit 2 are 720 and 329. They come out in the order they had after pass 1, which put 720 before 329. The earlier pass has already sorted by ones digit, and the tens pass keeps that order inside each tens group. When the last pass is done, the list is sorted by all three digits. If the passes were not stable, the ones digit order would be lost.

The digit of a number is found with two arithmetic steps. v // place removes the digits to the right of place, and % 10 keeps the last digit of what is left. For place = 10 and v = 457, 457 // 10 is 45, and 45 % 10 is 5, which is the tens digit. The double slash // is integer division, which drops the remainder.

The next program sorts with radix sort. It prints the list after each digit pass, so you can compare the steps with the table above.

The output is:

after the 1 digit pass: [170, 90, 802, 2, 24, 45, 75, 66]
after the 10 digit pass: [802, 2, 24, 45, 66, 170, 75, 90]
after the 100 digit pass: [2, 24, 45, 66, 75, 90, 170, 802]
sorted: [2, 24, 45, 66, 75, 90, 170, 802]

The line a[:] = out replaces every item of a with the items of out, and it keeps the same list object. The caller sees the change. Writing a = out would only make the name a point to a new list inside the function, and the caller's list would stay unchanged. This is one of the places where Python lists behave differently from variables that hold numbers.

Radix sort for numbers with d digits and a base of b (ten for decimal digits) costs about d times (n + b). For fixed-size numbers, d and b are constants, so the time is linear in n. This is why radix sort is used for large sets of fixed-width keys, such as IP addresses, dates written as digits, and some database keys. The tradeoff is that the code is more involved, and the extra memory for each pass is O(n + b).

Comparing the costs with real numbers

Big-O notation hides the constants, so it helps to put actual numbers next to each other. The table below counts rough steps. A comparison sort, such as Python's sorted(), needs about n times log base 2 of n steps. Counting sort needs about n plus k steps, where k is the range.

Read the table row by row. The first row looks like a win for counting sort, and it is. The third row is the trap. A million values is a lot of comparisons, but the range is so big that the boxes cost more than the comparisons would. The fourth row shows that a small list can be ruined the same way. Before you pick counting sort, look at k, not only at n.

The memory figure in the third row needs a note. A Python list stores a reference (the memory address of the item) for each box, and on a 64-bit computer each reference takes 8 bytes. A billion boxes need about 8 GB for the references alone, before any counts are stored. The exact size depends on your computer and Python version, so treat the figure as a rough scale.

The step counts are rough. They show the shape of the cost, not exact run times. Real time also depends on memory, so the table is a guide to choosing, not a benchmark. In Python, a loop of a million steps takes a noticeable fraction of a second, and the exact time depends on the machine.

What happens inside the machine

When counting sort runs, the computer spends most of its time in three simple loops. Each loop reads one list in order, which means it walks through neighbouring boxes in memory one after another. Sequential reading is fast, because the processor loads a block of nearby data into its cache at once. The cache is a small, fast memory close to the processor. Counting sort reads the input once, reads the count list once in order, and writes the output once in order. That is why it runs well in practice, even beyond its count of steps.

The count list is created with [0] * (biggest + 1). Python fills every box with zero when it creates the list, so you do not need a loop to set the boxes to zero. In a language such as C, the memory for a new array holds random leftover bytes, and the programmer must clear it. Python does that work for you, so the zeros come from the * 0 in the expression.

Memory is the real limit. A Python list of 4 billion boxes needs about 32 GB for its references alone. Most laptops cannot allocate that, so the program fails with a MemoryError or swaps to disk and becomes extremely slow. Before you choose counting sort, check the size of the range, not just the number of items.

Common mistakes and their messages

Mistake 1: making the list one box too short. A common error is [0] * biggest instead of [0] * (biggest + 1). The value biggest needs its own box, at index biggest. If the largest value is 8, the list needs indexes 0 to 8, which is nine boxes. With the short list, the tally line fails on the value 8. This program shows the message:

The output is:

Traceback (most recent call last):
  File "short.py", line 7, in <module>
    counting_sort([4, 2, 8])
    ~~~~~~~~~~~~~^^^^^^^^^^^
  File "short.py", line 5, in counting_sort
    count[v] += 1
    ~~~~~^^^
IndexError: list index out of range

Read it from the bottom. The last line says IndexError: list index out of range, which means an index was too large for the list. The line above it shows the code that failed. The first path depends on where you saved the file. The fix is to add one, so the list has biggest + 1 boxes.

Mistake 2: passing negative values straight in. The version that does not shift the values does not raise an error for small negative numbers. It reads the wrong boxes, as the earlier example showed, and prints a list with values missing. The fix is the shift by the minimum. The rule is simple: if the smallest value can be below zero, subtract the minimum before you use a value as an index.

Mistake 3: forgetting the list is empty. If you call counting_sort on an empty list, the version with lowest = min(a) fails on the first line of the function:

The output is:

Traceback (most recent call last):
  File "empty.py", line 4, in <module>
    counting_sort([])
    ~~~~~~~~~~~~~^^^^
  File "empty.py", line 2, in counting_sort
    lowest = min(a)
ValueError: min() iterable argument is empty

The last line says min() cannot find a smallest value in an empty sequence. Check if not a: return first. The loops would be fine with an empty list, but min and max need at least one value.

Mistake 4: going forwards in the stable version. Changing for i in reversed(range(len(keys))): to a forward loop still produces a sorted list, but the ties come out in the wrong order. The debugging section below shows the output.

Mistake 5: ignoring the range. Sorting five values where one value is 2,000,000,000 needs a tally list of about 2 billion boxes. The program is correct in principle, and the wrong choice is to use the method at all. Look at the range first. If the range is much bigger than the number of items, use a comparison sort such as sorted().

Mistake 6: using a letter as an index. The expression freq[ch] uses the character itself as the index. Python tries to use the string "a" as a list index, and it refuses:

The output is:

Traceback (most recent call last):
  File "letters.py", line 3, in <module>
    freq[ch] += 1
    ~~~~^^^^
TypeError: list indices must be integers or slices, not str

The message says a list index must be a whole number, and it found a string. The fix is freq[ord(ch) - ord("a")]. Compare this with the first lesson: a dictionary accepts text keys, but a list accepts only numbers.

Debugging walkthrough

Here is a stable counting sort with a bug. The loop that places the items goes forwards instead of backwards. The rest of the code is the same as the working version.

def stable_counting_order(keys, biggest):
    count = [0] * (biggest + 1)
    for k in keys:
        count[k] += 1
    for i in range(1, biggest + 1):
        count[i] += count[i - 1]
    order = [0] * len(keys)
    for i in range(len(keys)):               # BUG: forwards, not backwards
        count[keys[i]] -= 1
        order[count[keys[i]]] = i
    return order
 
names = ["Asha", "Ravi", "Meera", "Dev", "Kiran"]
marks = [72, 91, 72, 60, 91]
for idx in stable_counting_order(marks, 100):
    print(names[idx], marks[idx])

The program prints:

Dev 60
Meera 72
Asha 72
Kiran 91
Ravi 91

The list is sorted by mark, so a quick check passes. Only a careful look at the ties shows a problem. Meera came after Asha in the input, but now she comes first. Kiran also moved ahead of Ravi. The bug is the loop direction.

Trace it to see why. Forward, the loop meets Asha (key 72) first, and she takes the last slot of the 72 block. Then Meera (key 72) takes the slot before that. So the later item lands first. Going backwards reverses this, because the last item of the input is placed at the end of its block first.

Use this method when a sort looks right but the tests fail on ties:

1. Pick two items with the same key and label them with their input order.
2. Trace the algorithm on just those two items.
3. Check which one lands first.
4. Look for the loop direction, the comparison operator, or the place where the counter moves.

A change that looks harmless, such as flipping a loop direction, often explains the whole failure.

Variations and edge cases

• Values that repeat many times. Counting sort is at its best when the values repeat, because the tally captures the repeats in one number. A list of one million marks from 0 to 100 takes about 1,000,000 steps to tally, then 101 box checks and one million writes to write back.
• Values with no repeats in a big range. The method wastes the tally list. Use a comparison sort instead.
• A single value. Every value goes into one box. The write-back writes it n times and stops.
• Maximum equals zero. The list has one box, and the sorted output is just zeros.
• Huge but sparse ranges. Some problems give values like 10 and 1,000,000,000 in a list of two. A dictionary from value to count avoids the big list, but that is a different data structure, and you will meet it in a later module.

Finding the most common value

The tally answers questions without any sorting at all. The most common value in a list, called the mode, is one example. Keep the tally as you go, and remember the box with the biggest count so far. You never need the sorted list.

The output is:

2

Trace it on [4, 2, 2, 8, 3, 3, 1], with biggest equal to 8. Start with best = 4. Reading 4 makes its count 1, which is not more than the count of 4 (also 1), so best stays 4. Reading 2 makes its count 1, no change. Reading the second 2 makes its count 2, which is more than the count of best (1), so best becomes 2. After that, the 8 and the first 3 and the 1 each have count 1. The second 3 raises its count to 2, which only ties with the count of best, so best stays 2. The function returns 2, and it runs in O(n + biggest) time with one pass over the input.

The function takes the first value that reaches the top count, so ties are resolved by input order. Say which rule you use when an interviewer asks, because the question may not say.

Testing a counting sort

Counting sort has more edge cases than most sorts, so test it on purpose. The most reliable test compares your function with a trusted one on many random inputs. Here the trusted function is Python's sorted(). If the two outputs differ, the random input gives you a starting case to trace.

The output is:

trials: 500 failures: 0

The fixed seed 7 makes the random numbers the same on every run, so a failure can be repeated. The test includes the empty list, lists with one value and lists with negative values. Add the cases by hand as well. Test an empty list, a list with one value, a list where every value is equal, a list with negative values, and a list where the maximum equals the minimum. Each one breaks a different line of the function if the line is wrong.

Write the test before you trust the function, and keep it. Every later change to the sort should pass the same test, because a counting sort is easy to break with a small edit to a loop bound.

A close relative: bucket sort

Bucket sort is a related idea that handles values which are not whole numbers. Suppose the values are decimals between 0 and 1, spread evenly. Make ten buckets, one for each tenth. Put each value into the bucket for its first digit. A value such as 0.37 goes into bucket 3. Then sort each small bucket with insertion sort, and join the buckets in order.

Bucket sort is fast when the values are spread evenly, because each bucket holds only a few values, and sorting a few values is cheap. It is slow when most values land in one bucket, because then one insertion sort does most of the work, and the method falls back to O(n squared). The difference from counting sort is that a bucket holds a list of values, not a single count. Counting sort needs the values to be whole numbers, and bucket sort does not.

Interview questions

Question: Can you sort faster than n log n? Answer: yes, when you know something about the values. Counting sort and radix sort run in linear time for whole numbers in a small range or with a fixed number of digits. A comparison sort cannot beat n log n in the worst case. A good answer names both facts and says why the assumption on the values is the reason.

Question: How many boxes do you need to sort ages from 0 to 120 for a million people? Answer: 121 boxes. The number of people does not change the box count. The time is about 1,000,000 + 121 steps.

Question: How do you check whether two words are anagrams in linear time? Answer: build a 26-box count for each word and compare the lists. Equal counts mean an anagram. The time is O(n) for words of length n.

Question: Why is counting sort not in-place? Answer: it needs the output list, or at least the tally list, which is extra memory. The tally list has size k, so the extra space is O(k). Being in-place means using only a fixed amount of extra memory, which counting sort does not do. The version in this lesson writes the result back into the same list, but it still needs the tally list.

Question: A list holds one million numbers, and every number is between 0 and 999. How do you sort it, and what is the cost? Answer: counting sort with 1000 boxes. Tally in one pass, which is 1,000,000 steps, then write back, which is 1000 box checks plus one million writes. The total is O(n + k) with k equal to 1000, which is far less than n log n here. A strong answer also says that the boxes are cheap, because 1000 small integers take only a few kilobytes.

Question: You need to sort by age, and the people are listed with names. Does counting sort still work? Answer: yes, with the stable version. Use the age as the key, keep the names in a parallel list, and build the order of original indexes exactly as the lesson does. The names stay with their ages, and people with the same age keep their input order. If the ages were the only data, the simple version would do.

Real-world uses

Counting sort appears in graphics, where pixel intensities run from 0 to 255 and a histogram of the picture is a counting step. Image editors use that histogram to adjust brightness and contrast. Search tools count word frequencies, and the same idea sorts the results by count.

Radix sort is used in some databases and in high-speed sorting on graphics chips, because the digit passes map well to parallel hardware. Spell checkers and anagram finders count letters, the way the letter program above does.

Practice

Try each exercise on paper or in a file first. Check your answer after you have made an attempt.

1. Counting-sort [0, 5, 5, 2, 0, 1] by hand. Write the tally list (indexes 0 to 5) and the sorted output.

Show the answer

The tally list is [2, 1, 1, 0, 0, 2]. Index 0 holds 2 (two zeros), index 1 holds 1, index 2 holds 1, indexes 3 and 4 hold 0, and index 5 holds 2. The sorted output is [0, 0, 1, 2, 5, 5].

2. Change the first counting_sort so it prints the count list after the tally step. Run it on [4, 2, 2, 8, 3, 3, 1] and check that the boxes match the trace in this lesson.

Show the answer

Add print(count) right after the tally loop. The output is [0, 1, 2, 2, 1, 0, 0, 0, 1], which matches the trace: index 1 holds 1, index 2 holds 2, index 3 holds 2, index 4 holds 1 and index 8 holds 1.

3. Count the letters in Mississippi after converting it to lowercase. Print each letter that appears, in alphabetical order, with its count.

Show the answer

Convert with word.lower() first. The letters and counts are i: 4, m: 1, p: 2 and s: 4. The program in this lesson already prints them in that order, because it reads the boxes from a to z.

4. The students Ana 80, Bo 70 and Cy 80 are listed in that order. Use the stable counting method by hand to sort them by mark, lowest first, keeping ties in input order.

Show the answer

Tally: count[70] is 1 and count[80] is 2. Prefix sums: count[70] stays 1 and count[80] becomes 3. Backwards: Cy (80) goes to position 2 and count[80] drops to 2. Bo (70) goes to position 0 and count[70] drops to 0. Ana (80) goes to position 1. The order is Bo, Ana, Cy.

5. Explain in your own words why going backwards keeps equal items in their input order.

Show the answer

The backwards loop meets the last item of each key first. It places that item at the end of its block, then moves the block's end one step left. Each earlier item of the same key goes one step further left, so the input order is kept. Going forwards reverses the ties.

6. Explain why the counting sort in this lesson has O(n + k) time even though it has three loops.

Show the answer

The loops run one after another, not inside one another. The tally loop runs n times, the prefix or write-back loop runs k times, and the write-back of values adds up to n writes. Adding n + k + n gives a term of the same size as n + k. Nested loops over both n and k would be O(n times k), which is a different and much slower method.

7. A school has two million students and marks from 0 to 100. Compare counting sort with sorted() for sorting the marks. Which would you use, and why?

Show the answer

Counting sort needs about 2,000,000 + 101 steps and a 101-box list. sorted() needs about 2,000,000 times log base 2 of 2,000,000, which is roughly 42 million comparisons. Counting sort is faster and needs very little memory. Either works, but counting sort is the better fit because the range is tiny.

8. Write a function print_duplicates(a, biggest) that prints each value from 0 to biggest that appears more than once, in increasing order.

Show the answer

def print_duplicates(a, biggest):
    count = [0] * (biggest + 1)
    for v in a:
        count[v] += 1
    for v in range(biggest + 1):
        if count[v] > 1:
            print(v)

The function runs in O(n + biggest) time.

9. Use LSD radix sort by hand on [170, 45, 75, 90, 802, 24, 2, 66]. Write the list after the ones pass, the tens pass and the hundreds pass.

Show the answer

After the ones pass: [170, 90, 802, 2, 24, 45, 75, 66]. After the tens pass: [802, 2, 24, 45, 66, 170, 75, 90]. After the hundreds pass: [2, 24, 45, 66, 75, 90, 170, 802]. The tens pass changes order inside each group, but the groups stay in the order the ones pass left them. The radix sort program earlier in this lesson prints the same three lists.

10. Write sort_letters(s) that sorts a list of lowercase letters in place with counting sort, in O(n) time. Test it on list("dcabca").

Show the answer

def sort_letters(s):
    count = [0] * 26
    for c in s:
        count[ord(c) - ord("a")] += 1
    idx = 0
    for k in range(26):
        for _ in range(count[k]):
            s[idx] = chr(ord("a") + k)
            idx += 1

The first loop reads the input once, and the second writes it once plus 26 box checks. Running it on list("dcabca") gives ['a', 'a', 'b', 'c', 'c', 'd'], which joins to aabccd.

What you now know

• Comparison sorts need about n log n comparisons in the worst case. Counting sort avoids comparisons by counting values in a small known range.
• The tally list has one box per possible value. Its size is the range, highest - lowest + 1, and that range must be small.
• Shift values by the minimum to handle negative numbers. A negative index in Python does not raise an error, so the shift is what keeps the counts correct.
• A stable counting sort uses a prefix sum and fills the output from the back. Going backwards keeps ties in input order.
• Counting letters is counting sort on a 26-box list, using ord and chr to convert between letters and numbers. Radix sort applies stable counting one digit at a time.
• Counting sort runs in O(n + k) time and uses O(k) extra space, so it is right when the range is small and wrong when the range is huge.