Counting sort is a lightning fast way to organize items when their values are small, whole numbers, by simply counting how many of each item you have.

Key idea: Counting sort works by counting the occurrences of each unique value in the list, rather than comparing items.

Imagine you have a basket full of different colored toy blocks: 3 red, 2 blue, 5 green, and 1 yellow. If you wanted to sort them by color, you would not compare 'red' to 'blue' directly. Instead, you would just count how many of each color you have. You would say, "Okay, I have 3 red blocks, 2 blue blocks, 5 green blocks, and 1 yellow block." This is the core idea behind counting sort.

Instead of comparing items, counting sort first creates a temporary storage space, like a set of empty buckets, one for each possible value your items can have. If your numbers range from 0 to 10, you would have 11 buckets. Then, it goes through your original list of items and, for each item, it simply adds a tally mark to the correct bucket. So, if you see the number 5, you add one to the '5' bucket. If you see another 5, you add another tally to the '5' bucket.

After going through all your items, each bucket will hold a count of how many times its number appeared in your original list. For example, if the '5' bucket has 3 tally marks, it means the number 5 appeared 3 times in your original list.

Key idea: A prefix sum calculation helps determine the exact starting position for each group of identical numbers in the final sorted list.

Now that we know how many of each number we have, how do we actually sort them? This is where a clever trick called a prefix sum comes in. Think back to our toy blocks. After counting them, you know you have 3 red, 2 blue, 5 green, and 1 yellow. If you wanted to arrange them in order (say, yellow, blue, red, green), you would first place the 1 yellow block. Then, the 2 blue blocks would come after the yellow one. So, the blue blocks would start at position 2 (after the first yellow block). The 3 red blocks would come after the blue ones, starting at position 4 (after 1 yellow + 2 blue). And so on.

A prefix sum helps us figure out exactly where each group of numbers should start in the final sorted list. We take our counts (e.g., 3 for red, 2 for blue, etc.) and turn them into 'starting positions.' The first count stays the same. The second count becomes itself plus the first count. The third count becomes itself plus the previous total, and so on. This tells us the end position for each number, and by subtracting one, we get its starting position.

For example, if we have counts: 1 (for 0), 2 (for 1), 3 (for 2). The prefix sum would be: 1 (for 0), 1+2=3 (for 1), 3+3=6 (for 2). This means the number 0 takes up the first spot. The numbers 1 take up spots 2 and 3. The numbers 2 take up spots 4, 5, and 6. This way, we know exactly where to put each item in the final sorted list.

“A prefix sum helps us figure out exactly where each group of numbers should start in the final sorted list.”

Key idea: The final step involves placing each item into its correct, calculated position in the output list, moving backwards through the original list to maintain stability.

With our counts and starting positions ready, the final step is to actually build the sorted list. We go through our original, unsorted list of items, but we do it backwards. Why backwards? Because this helps us keep the original order of items that have the same value. This is called a stable sort, which is important in many computer tasks.

As we pick an item from the original list (starting from the end), we look up its value in our 'starting positions' information. That tells us exactly where it belongs in the new, sorted list. We place the item there, and then we reduce the count for that value by one, so the next item with the same value goes into the spot just before it. We repeat this until all items are moved to their correct, sorted positions.

Let's say we have the numbers [4, 2, 1, 4, 2].

1. Count: 1 (for 1), 2 (for 2), 0 (for 3), 2 (for 4).

2. Prefix sum (adjusted for starting position): 0 (for 1), 1 (for 2), 3 (for 3), 3 (for 4).

3. Now, we place items from the original list, going backwards:

The last item is 2. Its position is 1. Sorted list: [_, 2, _, _, _]. Update count for 2 to 0.

Next is 4. Its position is 3. Sorted list: [_, 2, _, 4, _]. Update count for 4 to 2.

Next is 1. Its position is 0. Sorted list: [1, 2, _, 4, _]. Update count for 1 to 0.

Next is 2. Its position is 0 (after previous update). Sorted list: [1, 2, 2, 4, _]. Update count for 2 to -1 (this is why we subtract first, then place).

Next is 4. Its position is 2. Sorted list: [1, 2, 2, 4, 4]. Update count for 4 to 1.

The final sorted list is [1, 2, 2, 4, 4]. This process is very direct and avoids complex comparisons.

Here is the algorithm in action:

“We go through our original, unsorted list of items, but we do it backwards. Why backwards? Because this helps us keep the original order of items that have the same value.”

Key idea: Counting sort is very fast, but only efficient when the range of values is not significantly larger than the number of items being sorted.

One of the most amazing things about counting sort is how fast it is. Unlike many other sorting methods that slow down a lot as the number of items grows, counting sort can sort a list in a time that grows linearly with the number of items and the range of their values. Think of it this way: if you double the number of items, it roughly takes twice as long. If you double the range of values (e.g., from 0 to 100 to 0 to 200), it also roughly takes twice as long.

This speed comes from the fact that it does not do any complex comparisons. It just counts and places. However, this also highlights its main limitation: it works best when the range of possible values (let's call this 'k') is not much larger than the number of items you are sorting (let's call this 'n'). If you have only 10 items but their values can go up to a million, creating a million 'buckets' to count them would be a huge waste of space and time.

So, counting sort is a specialized tool. It is perfect for tasks like sorting exam scores (0 to 100) or ages (0 to 120), where the range of values is small and fixed.

Key idea: Counting sort is often used as a fast helper in other sorting algorithms like radix sort, which can handle larger numbers more effectively.

Counting sort is often used as a helper in another powerful sorting method called radix sort. Radix sort can handle much larger numbers by breaking them down into digits and then using counting sort to sort based on each digit, one at a time. Imagine sorting a list of phone numbers: you might first sort them by the last digit, then by the second to last digit, and so on, using counting sort for each digit.

This combination allows radix sort to handle very large numbers efficiently, making counting sort a crucial building block in many advanced sorting applications. It is a testament to how a simple, specialized tool can become part of a much larger and more powerful system.