Understanding counting sort algorithm

The strategy from the earlier example (stacking answer sheets by score and then unwinding the stacks in order) could be used to create an algorithm. To explain this algorithm, we will take an array as an input list, but the same algorithm can be applied to any list data structure.

Algorithm

The array is sorted by counting the frequency of each distinct element (often called its key, since each value is used to look up a position in the count array) and then using this information to determine the correct position of each element in the sorted output. Unlike comparison-based sorting algorithms, counting sort works by directly mapping values to their positions, making it especially efficient when the range of input values is limited.

The algorithm consists of three main steps, each of which is crucial to transforming the input list into a fully sorted output.

• Step 1: Calculate the frequency of each element.
• Step 2: Calculate the cumulative sum of frequencies.
• Step 3: Build the sorted output.

Step 1: Calculate the frequency of each element