Interview Cake by Exponent
The input [1, 3, 7, 8, 1, 1, 3] has three (1)'s, two (3)'s, and a (7) and (8). Encoding that in a list of counts, we have [0, 3, 2, 0, 0, 0, 1, 1, 0, 0].

Counting Sort Algorithm

Sorting Algorithm

In short: Counting sort sorts integers by counting how many times each value appears, then using those counts to place each item directly into its sorted position. It runs in O(n + k) time, where k is the range of values, and isn't comparison-based.

Quick reference

Complexity
Worst case time
Best case time
Average case time
Space

Strengths:

  • Linear time. Counting sort runs in time, making it asymptotically faster than comparison-based sorting algorithms like quicksort or merge sort.

Weaknesses:

  • Restricted inputs. Counting sort only works when the range of potential items in the input is known ahead of time.
  • Space cost. If the range of potential values is big, then counting sort requires a lot of space (perhaps more than ).

The High-Level Idea

Counting sort works by iterating through the input, counting the number of times each item occurs, and using those counts to compute an item's index in the final, sorted list.

Counting How Many Times Each Item Occurs

Say we have this list:

Unsorted input: [4, 8, 4, 2, 9, 9, 6, 2, 9].

And say we know all the numbers in our list will be whole numbers between 0 and 10 (inclusive).

The idea is to count how many 0's we see, how many 1's we see, and so on. Since there are 11 possible values, we'll use a list with 11 counters, all initialized to 0.

Couldn't we use a dictionary instead? We could, but since we're working with items that can easily be mapped to list indices, using a list is a bit more lightweight. Remember: dictionaries are built on top of lists.

List of counters: [0 zeros, 0 ones, 0 twos, 0 threes, 0 fours, 0 fives, 0 sixes, 0 sevens, 0 eights, 0 nines, 0 tens].

We'll iterate through the input once. The first item is a 4, so we'll add one to counts[4]. The next item is an 8, so we'll add one to counts[8].

The first two elements in the input [4, 8, 4, 2, ...] are 4 and 8. To count them, we increment the value at indices 4 and 8 in our counts list, which becomes [0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0].

And so on. When we reach the end, we'll have the total counts for each number:

Once we count all the values in [4, 8, 4, 2, 9, 9, 6, 2, 9], the counts list is [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

Building the Sorted Output

Now that we know how many times each item appears, we can fill in our sorted list. Looking at counts, we don't have any 0's or 1's, but we've got two 2's. So, those go at the start of our sorted list.

Our sorted output is [2, 2, _, _, _, _, _, _, _], because we counted two (2)'s in the input.

No 3's, but there are two 4's that come next.

Accounting for the two (4)'s, the sorted output becomes [2, 2, 4, 4, _, _, _, _, _].

After that, we have one 6,