[Verse 1]
Listen up, we got a sorting algorithm that's clean
No comparisons needed, it's the fastest you've seen
Takes your integers, breaks them down digit by digit
Stable sorting power, yeah you know we're gonna get it
Start from the least significant, that's the rightful place
Counting sort on each position, keeping perfect pace
Linear time complexity when the range is right
Radix sort's the champion when your data's finite
[Chorus]
Digit by digit, we're sorting tonight
LSD to MSD, keeping order tight
Counting sort buckets, redistribute the load
Radix sort's the method, it's the optimal code
Least significant first, then we work our way up
O of n times k, fill that sorting cup
[Verse 2]
Create your buckets, zero through nine in a row
Count the frequencies, let the histogram grow
Stable sorting matters, keep the relative stance
Same key elements maintain their original dance
Decimal base ten, but binary works too
Hexadecimal sorting, radix handles it through
When your keys are integers and the range is bound
Radix sort's efficiency is the best around
[Chorus]
Digit by digit, we're sorting tonight
LSD to MSD, keeping order tight
Counting sort buckets, redistribute the load
Radix sort's the method, it's the optimal code
Least significant first, then we work our way up
O of n times k, fill that sorting cup
[Bridge]
Most significant digit when you need early stopping
Lexicographic order, keep those strings from dropping
Space complexity's linear, memory we consume
But the speed that we deliver makes our algorithms bloom
No divide and conquer, no recursive calls
Just systematic bucketing through numerical halls
[Verse 3]
Pass through every digit position, left to right we go
Counting sort as subroutine, maintaining stable flow
When k is small and n is large, we dominate the game
Linear sorting power, that's our radix claim to fame
Fixed-width integers, that's our sweet spot zone
Character strings and records, radix stands alone
[Chorus]
Digit by digit, we're sorting tonight
LSD to MSD, keeping order tight
Counting sort buckets, redistribute the load
Radix sort's the method, it's the optimal code
Least significant first, then we work our way up
O of n times k, fill that sorting cup
[Outro]
When comparison sorts hit n log n ceiling
Radix breaks the barrier with that linear feeling
Digit by digit, that's the radix way
Stable sorting champion, every single day