Counting Sort Algorithm

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 array.

Counting How Many Times Each Item Occurs

Say we have this array:

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

And say we know all the numbers in our array 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 an array with 11 counters, all initialized to 0.

Couldn't we use a hash map instead? We could, but since we're working with items that can easily be mapped to array indices, using an array is a bit more lightweight. Remember: hash maps are built on top of arrays.

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 array. 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 array.

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,

Accounting for the single (6), the sorted output becomes [2, 2, 4, 4, 6, _, _, _, _].

one 8,

Accounting for the single (8), the sorted output becomes [2, 2, 4, 4, 6, 8, _, _, _].

and three 9's

Finally, our three (9)'s go at the end: [2, 2, 4, 4, 6, 8, 9, 9, 9].

And, with that, we're done!

Final sorted output: [2, 2, 4, 4, 6, 8, 9, 9, 9].

Handling Non-Numeric Items

What if the items in our input aren't simple numbers that we can extract from our counts array?

As an example, what if we had an array of dessert objects, and we wanted to sort them by price?

[(type: macadamia nut cookie, price: 4), (type: double chocolate cake, price: 8), (type: chocolate chip cookie, price: 4), (type: sugar cookie, price: 2), (type: creme brulee, price: 9), (type: chocolate souflee, price: 9), (type: fruit tart, price: 6), (type: brownie, price: 2), (type: eclair, price: 9)]

We'll use these icons to represent the objects:

Unsorted Input with prices: [M $4, DCC $8, CCC $4, S $2, CB $9, CS $9, FT $6, B $2, E $9].

If we went through and counted up all the prices, we'd end up with the same counts array.

Count list for prices: [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

But when we go to add the 2's into our sorted array, we need to get the actual dessert objects.

There are a few ways we could do this:

Iterate through the input to find both of the desserts that cost $2. That takes time for each cost, so time overall.
Build a hash map mapping prices to desserts. (Maybe this could even replace counts.) We could do this without adding any asymptotic time cost, but this would basically be making an extra copy of the input, which would be extra space.

We can do this in time without any extra copies of the input.

Building a Next Index Array

Using our counts array, we can pre-compute where each item from the input should go. Then we'll just iterate through the input, using the pre-computed indices to place each item in the right spot.

We'll use our counts array to build up another array, nextIndex, that will track where the next occurrence of a price goes in our sorted output. For instance, nextIndex[4] would hold the index for the next item with a price of $4.

Hold up. Doesn't this add space to our algorithm?

Hang tight ... we'll see that with some cleverness we won't need a separate array for nextIndex after all.

We can initialize nextIndex from our counts array.

The lowest price is $2, so the $2 items will start at index 0. (Nothing costs $0 or $1, so we'll just set those to 0.)

Counts list: [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0]. Next Index list: [0, 0, 0, _, _, _, _, _, _, _].

Items that cost $3 go after all the items that cost $2. Two items in the array cost $2, so they'll take up indices 0 and 1. That means the first $3 item would go at index 2.

The third index in Next Index is calculated by adding the second index of counts (2) and the second index of Next Index (0) to get 2. The Next Index list is now [0, 0, 0, 2, _, _, _, _, _, _, _]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

Notice how nextIndex[3] = nextIndex[2] + counts[2]. That makes sense, because we're taking the starting point for the $2 items and moving forward to make room for each of them. In general:

nextIndex[i] = nextIndex[i - 1] + counts[i - 1]

We can keep iterating through counts using this formula to fill in nextIndex.

The fourth index in Next Index is calculated by adding the third index of counts (0) and the third index of Next Index (2) to get 2. The Next Index list is now [0, 0, 0, 2, 2, _, _, _, _, _, _]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

The fifth index in Next Index is calculated by adding the fourth index of counts (2) and the fourth index of Next Index (2) to get 4. The Next Index list is now [0, 0, 0, 2, 2, 4, _, _, _, _, _]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

The sixth index in Next Index is calculated by adding the fifth index of counts (0) and the fifth index of Next Index (4) to get 4. The Next Index list is now [0, 0, 0, 2, 2, 4, 4, _, _, _, _]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

The seventh index in Next Index is calculated by adding the sixth index of counts (1) and the sixth index of Next Index (4) to get 5. The Next Index list is now [0, 0, 0, 2, 2, 4, 4, 5, _, _, _]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

The eigth index in Next Index is calculated by adding the seventh index of counts (0) and the seventh index of Next Index (5) to get 5. The Next Index list is now [0, 0, 0, 2, 2, 4, 4, 5, 5, _, _]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

The ninth index in Next Index is calculated by adding the eigth index of counts (1) and the eigth index of Next Index (5) to get 6. The Next Index list is now [0, 0, 0, 2, 2, 4, 4, 5, 5, 6, _]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

The tenth index in Next Index is calculated by adding the ninth index of counts (3) and the ninth index of Next Index (6) to get 9. The Next Index list is now [0, 0, 0, 2, 2, 4, 4, 5, 5, 6, 9]. Counts is still [0, 0, 2, 0, 2, 0, 1, 0, 1, 3, 0].

As we'll see, we actually don't need counts anymore after we've built nextIndex.

So instead of creating a separate array for nextIndex, we can just modify counts in-place in one pass to get our nextIndex array. It's slightly trickier, but it can be done :)

Building Our Sorted array With nextIndex

First up, we've got

It has a price of $4. Since nextIndex[4] is 2, we know it goes at index 2.

The first element in the unsorted input [M $4, DCC $8, CCC $4, S $2, CB $9, CS $9, FT $6, B $2, E $9] is (4). The value at the 4th index of Next Index is 2. So, the first element in the unsorted input goes at index 2 in the sorted output: [_, _, M $4, _, _, _, _, _, _].

And, since we've placed something at index 2, we now know that the next item that costs $4 goes after it, at index 3. So we'll increment nextIndex[4].

The value at the 4th index of Next Index is incremented from 2 to 3. Next Index is now [0, 0, 0, 2, 3, 4, 4, 5, 5, 6, 9].

Moving on to the next item, we've got

It costs $8. Since nextIndex[8] is 5, it goes at index 5:

The second element in the unsorted input [M $4, DCC $8, CCC $4, S $2, CB $9, CS $9, FT $6, B $2, E $9] is (8). The value at the 8th index of Next Index is 5. So, the second element in the unsorted input goes at index 5 in the sorted output: [_, _, M $4, _, _, DCC $8, _, _, _].

And we increment nextIndex[8]:

The value at the 8th index of Next Index is incremented from 5 to 6. Next Index is now [0, 0, 0, 2, 3, 4, 4, 5, 6, 6, 9].

Next comes . It also costs $4, just like .

The third element in the unsorted input [M $4, DCC $8, CCC $4, S $2, CB $9, CS $9, FT $6, B $2, E $9] is (4). The value at the 4th index of Next Index is 3. So, the third element in the unsorted input goes at index 3 in the sorted output: [_, _, M $4, CCC $4, _, DCC $8, _, _, _].

Good thing we incremented nextIndex[4] when we added to our sorted output! Else we'd just write our over at index 2 in our sorted output.

Speaking of, let's make sure we update nextIndex again:

The value at the 4th index of Next Index is incremented from 3 to 4. Next Index is now [0, 0, 0, 2, 4, 4, 4, 5, 6, 6, 9].

Next up :

The fourth element in the unsorted input [M $4, DCC $8, CCC $4, S $2, CB $9, CS $9, FT $6, B $2, E $9] is (2). The value at the 2nd index of Next Index is 0. So, the fourth element in the unsorted input goes at index 0 in the sorted output: [SC $2, _, M $4, CCC $4, _, DCC $8, _, _, _].

And we update nextIndex:

The value at the 2nd index of Next Index is incremented from 0 to 1. Next Index is now [0, 0, 1, 2, 4, 4, 4, 5, 6, 6, 9].

And so on, until we're done!

Implementation

Here's how we'd code it up:

public static int[] countingSort(int[] theArray, int maxValue) { // count the number of times each value appears. // counts[0] stores the number of 0's in the input // counts[4] stores the number of 4's in the input // etc. int[] counts = new int[maxValue + 1]; for (int item : theArray) { counts[item] += 1; } // overwrite counts to hold the next index an item with // a given value goes. so, counts[4] will now store the index // where the next 4 goes, not the number of 4's our // array has. int numItemsBefore = 0; for (int i = 0; i < counts.length; i++) { int count = counts[i]; counts[i] = numItemsBefore; numItemsBefore += count; } // output array to be filled in int[] sortedArray = new int[theArray.length]; // run through the input array for (int item : theArray) { // place the item in the sorted array sortedArray[ counts[item] ] = item; // and, make sure the next item we see with the same value // goes after the one we just placed counts[item] += 1; } return sortedArray; }

What if the values could be negative? Or the smallest value was 50?

Our implementation assumes that all of the items are between 0 and some maximum. But it's pretty simple to extend the algorithm to handle any sort of range of integers. Give it a try. :)

Complexity

Counting sort takes time and space, where n is the number of items we're sorting and k is the number of possible values.

We iterate through the input items twice—once to populate counts and once to fill in the output array. Both iterations are time. Additionally, we iterate through counts once to fill in nextIndex, which is time.

The algorithm allocates three additional arrays: one for counts, one for nextIndex, and one for the output. The first two are space and the final one is space.

You can actually combine counts and nextIndex into one array. No asymptotic changes, but it does save space.

In many cases cases, k is (i.e.: the number of items to be sorted is not asymptotically different than the number of values those items can take on. Because of this, counting sort is often said to be time and space.

Interview coming up?

Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.

No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe whenever.

You're in! Head over to your email inbox right now to read day one!