[Verse 1]
Got an unsorted array, chaos in the mix
Elements scattered like they're playing dirty tricks
But I got a strategy, divide and conquer clean
Split it down the middle, most efficient you've seen
Take the left half, take the right half too
Recursively break them down, that's what we do
Keep on splitting till you get to single nodes
Then we merge them back up, following the codes
[Chorus]
Divide and merge, divide and merge
Breaking down arrays then making them converge
O of n log n, that's the time we earn
Stable sorting guaranteed, watch the patterns turn
Divide and merge, divide and merge
Split it in the middle, let the order emerge
[Verse 2]
When you're merging back together, here's the master plan
Two sorted halves combine with a helping hand
Compare the first elements, pick the smaller one
Place it in result array, but we're not done
Move the pointer forward where the winner came
Keep comparing elements, playing merge game
Till one half is empty, then append the rest
Mergesort delivers results that are the best
[Chorus]
Divide and merge, divide and merge
Breaking down arrays then making them converge
O of n log n, that's the time we earn
Stable sorting guaranteed, watch the patterns turn
Divide and merge, divide and merge
Split it in the middle, let the order emerge
[Bridge]
Base case is single element, already sorted clean
Recursive calls build up the sorting machine
Extra space required, that's the trade we make
O of n memory for performance sake
Worst case, best case, average stays the same
Logarithmic levels in this sorting game
[Verse 3]
From the bottom up we build our sorted runs
Merging pairs of singles till the job is done
Then merge pairs of pairs, doubling every round
Most reliable sort that can ever be found
When stability matters and you need it fast
Mergesort's the algorithm that's built to last
Predictable performance, no quadratic fears
The divide and conquer champion for all these years
[Chorus]
Divide and merge, divide and merge
Breaking down arrays then making them converge
O of n log n, that's the time we earn
Stable sorting guaranteed, watch the patterns turn
Divide and merge, divide and merge
Split it in the middle, let the order emerge
[Outro]
Split it down the middle
Merge it back together
Mergesort forever
Divide and merge the answer