Summary

Counting Sort is an efficient, non-comparison-based sorting algorithm that works best when the range of input values ($k$) is not significantly greater than the number of elements ($n$). Unlike comparison sorts like Merge Sort or Quick Sort, it does not compare elements against each other. Instead, it counts the frequency of each distinct element and calculates their starting positions in the output array using prefix sums. This makes it a stable sort with linear time complexity relative to the input size and range.

How it Works

• Find the Range: Traverse the array to find the maximum value ($k$) to determine the size of the count array.

• Initialize Count Array: Create an auxiliary array cntArr of size $k+1$ initialized to zeros.

• Frequency Count: Traverse the input array. For each element, increment the corresponding index in cntArr.

• Prefix Sums: Modify cntArr by adding the value of the previous index to the current index. This step determines the position of elements in the sorted output.

• Build Output: Traverse the input array backwards (to maintain stability). For each element, look up its position in cntArr, place it in the output array, and decrement the count.