DSA Day 82: Merge Sort Analysis & Master's Theorem

📅 Date: July 13, 2026

🧠 Mood: The Logician 🧩

🔥 Topic: DSA Day 82: Merge Sort Analysis & Master's Theorem

📚 Decoding the Divide and Conquer

A few weeks ago, I wrote about Merge Sort. I knew it was fast, but today I actually had to prove *why* it's fast mathematically. The syllabus handed me a PDF on Master's Theorem, which is a direct formula used to calculate the time complexity of Divide and Conquer algorithms without drawing massive trees.

---

✂️ The $O(N \log N)$ Proof

Merge Sort does two things: it divides the array in half, and then it merges them.

Step-by-Step Breakdown

• The Division: Halving an array down to single elements takes $O(\log N)$ steps.
• The Merge: At each of those levels, the algorithm must touch every single element to merge them back together in sorted order. Touching every element takes $O(N)$ time.
• The Result: You multiply the work done per level by the number of levels: $O(N \log N)$.

This makes Merge Sort exponentially faster than Bubble Sort's $O(N^2)$ and is the exact reason it is highly favored in large-scale system processing. We also analyzed the optimized Power Function today, confirming its brilliant $O(\log N)$ performance.