[Verse 1]
Array scattered like fragments, chaos in sight
But mergesort whispers, "I'll make this right"
Divide and conquer, that's my ancient creed
Split down the middle till single elements feed
Recursive descent through logarithmic floors
Each partition shrinks while precision soars
Base case hits when length equals one
That's when the real magic has begun
[Chorus]
Merge like a zipper, two become one
Compare the smallest, pick and run
Left pointer, right pointer, dancing in sync
Stable and steady, faster than you think
O-n-log-n, that's my guarantee
Mergesort forever, algorithms set free
[Verse 2]
Temporary buffer holds the sorted pieces
While original array waits as tension releases
Left subarray versus right subarray clash
Winner takes the spot in a lightning flash
When one side empties, copy the rest
No element forgotten, every value blessed
Bottom-up building from atomic parts
Like crystalline structures, mathematical arts
[Chorus]
Merge like a zipper, two become one
Compare the smallest, pick and run
Left pointer, right pointer, dancing in sync
Stable and steady, faster than you think
O-n-log-n, that's my guarantee
Mergesort forever, algorithms set free
[Bridge]
Quicksort might stumble on worst-case terrain
Bubble sort drowns in quadratic pain
But I stay consistent through thick and thin
Space complexity trades for the certain win
External sorting when memory runs low
Disk-based merging with sequential flow
[Verse 3]
Sentinel values guard against overflow
Infinite markers where boundaries go
Inversion counting rides along my spine
Measuring disorder in linear time
Parallel processing splits my workload
Multi-threaded sorting on the superhighway road
[Chorus]
Merge like a zipper, two become one
Compare the smallest, pick and run
Left pointer, right pointer, dancing in sync
Stable and steady, faster than you think
O-n-log-n, that's my guarantee
Mergesort forever, algorithms set free
[Outro]
When chaos needs order and speed matters most
I'm the algorithm that computers toast
Divide, conquer, merge, repeat
Mergesort makes sorting complete