[Verse 1]
Array scattered like puzzle pieces on the floor
Choose a pivot, random element from the core
Partition time, rearrange the scattered crowd
Smaller left, bigger right, divide and conquer loud
Tony Hoare invented this recursive machine
Split the problem, conquer halves, algorithmic dream
[Chorus]
Quick-sort, quick-sort, divide and you shall reign
Pivot splits the battlefield, smaller problems remain
Quick-sort, quick-sort, O of n log n the game
Worst case quadratic but average breaks the chain
[Verse 2]
Lomuto scheme or Hoare's original design
Two pointers dancing, crossing over the divide
In-place magic, no extra memory to steal
Swap elements, maintain the partition seal
Recursion stack grows deep when pivot picks poorly
Choose median-of-three, performance soars surely
[Chorus]
Quick-sort, quick-sort, divide and you shall reign
Pivot splits the battlefield, smaller problems remain
Quick-sort, quick-sort, O of n log n the game
Worst case quadratic but average breaks the chain
[Bridge]
Base case hits when subarray shrinks to one
Recursion unwinds, the sorting work is done
Cache-friendly access, locality preserved
Modern processors love the patterns observed
Randomized pivot kills the worst-case curse
Introsort hybrid when recursion gets perverse
[Verse 3]
Tail recursion optimization cuts the stack
Iterative version brings the memory back
Unstable sort but comparison-based and clean
Practical choice for massive data scenes
Three-way partition handles duplicate keys
Dutch flag problem solved with elegant ease
[Chorus]
Quick-sort, quick-sort, divide and you shall reign
Pivot splits the battlefield, smaller problems remain
Quick-sort, quick-sort, O of n log n the game
Worst case quadratic but average breaks the chain
[Outro]
Conquer through division, ancient wisdom applied
Algorithm mastery with recursion as guide