[Verse 1]
Check the data first, what's the range we see
From minimum to maximum, that's the key
If the spread is wide, counting sort won't fly
But when numbers are tight, we reach for the sky
Create an array based on the range size
Initialize to zero, that's no surprise
Linear time complexity when K is small
But space can grow large, gotta watch that call
[Chorus]
Count it up, count it down, frequency's the way
Stable sort in linear time when the range is okay
Count it up, sum it up, prefix makes it right
Counting sort delivers when the data's tight
O of N plus K, that's the time we need
Space complexity K, plant that sorting seed
[Verse 2]
First pass through the input, count each element
Increment the bucket where each number went
Second pass is crucial, make it cumulative
Each position tells us where the item lives
The prefix sum array shows the final spot
For each value's placement, it hits the dot
Work backwards through input to keep it stable
Same values maintain order, that's the label
[Chorus]
Count it up, count it down, frequency's the way
Stable sort in linear time when the range is okay
Count it up, sum it up, prefix makes it right
Counting sort delivers when the data's tight
O of N plus K, that's the time we need
Space complexity K, plant that sorting seed
[Bridge]
When K is much larger than N itself
Put counting sort back on the shelf
But for integers in a bounded space
This algorithm takes first place
No comparisons needed here
Just arithmetic crystal clear
[Verse 3]
Place each element using the prefix guide
Decrement the counter as we slide inside
Building up the output from right to left
Stability preserved, no order theft
Perfect for when data has limited scope
Radix sort foundations, it gives us hope
Non-comparison sorting at its best
Linear time performance passes every test
[Chorus]
Count it up, count it down, frequency's the way
Stable sort in linear time when the range is okay
Count it up, sum it up, prefix makes it right
Counting sort delivers when the data's tight
O of N plus K, that's the time we need
Space complexity K, plant that sorting seed
[Outro]
Three simple phases make the magic work
Count, prefix, place - no need to lurk
When the range is right and data's dense
Counting sort makes perfect sense