[Verse 1]
Got an array of numbers, all within a bound
From zero to some max value, that's where power's found
First we build a counting array, size of range plus one
Initialize with zeros, that's how we begun
Walk through every element in our input set
Count frequency of each value, don't forget to get
Every single occurrence stored in proper place
Counting array holds the key to sorting with such grace
[Chorus]
Count the frequencies, that's step number one
Build that counting array until the count is done
Cumulative sum it up, positions now we know
Place them in their final spots, watch the sorted flow
Count, accumulate, and place
Linear time, we win the race
Stable sort when done with care
Counting sort beyond compare
[Verse 2]
Now we modify our counts to cumulative form
Each position tells us where each element belongs
Starting from the second slot, add the one before
Building up the prefix sums, that's the counting core
Walk backwards through input, maintaining stable nature
Place each element where counts array shows its future
Decrement the count each time, making room for more
Same values stay in order, that's what stable's for
[Chorus]
Count the frequencies, that's step number one
Build that counting array until the count is done
Cumulative sum it up, positions now we know
Place them in their final spots, watch the sorted flow
Count, accumulate, and place
Linear time, we win the race
Stable sort when done with care
Counting sort beyond compare
[Bridge]
Space complexity trade-off, memory for the speed
Range size matters most, that's what you need to heed
When the range is reasonable, counting sort's your friend
Linear performance guaranteed from start to end
Not comparison based, we count instead of compare
O of n plus k runtime, efficiency we share
[Verse 3]
Perfect for those situations when you know the bounds
Grades from zero to hundred, where efficiency's found
Character frequencies, histogram creation
Radix sort foundation, digit separation
But beware the memory usage when the range grows wide
Sparse data wastes space, choose your algorithm guide
Integers are required, floats need not apply
Counting sort's domain is clear, now you know just why
[Chorus]
Count the frequencies, that's step number one
Build that counting array until the count is done
Cumulative sum it up, positions now we know
Place them in their final spots, watch the sorted flow
Count, accumulate, and place
Linear time, we win the race
Stable sort when done with care
Counting sort beyond compare
[Outro]
Three simple steps and you're done
Count, accumulate, place each one
When the range is small and tight
Counting sort will treat you right
Linear time complexity
That's the counting guarantee