The Quest Begins (The "Why")
I still remember the first time I got hit with a sorting question in an interview. The interviewer slid a whiteboard marker across the table and said, “Sort this array of a million integers – and tell me why you chose your method.” My brain went straight to the trusty old bubble sort I’d learned in CS101. I started writing nested loops, feeling like Neo dodging bullets in slow motion, only to realize the runtime was creeping toward O(n²). After a few painful minutes, I could see the interviewer’s eyes glaze over – not because I was wrong, but because I was using a sledgehammer to crack a nut.
That moment sparked a quest: What makes a sorting algorithm truly efficient, and how do I know when to reach for it? I dove into textbooks, blog posts, and late‑night YouTube deep dives. The answer kept pointing back to one algorithm that felt like discovering a hidden cheat code: Merge Sort.
The Revelation (The Insight)
So why does Merge Sort work so well? It’s not just about splitting and merging; it’s about guaranteeing that each level of recursion does a linear amount of work, no matter how the input is arranged.
