DSA Day 69: Divide & Conquer (Merge Sort)

📅 Date: June 20, 2026

🧠 Mood: The Surgeon 🔪

🔥 Topic: DSA Day 69: Divide & Conquer (Merge Sort)

✂️ Recursion on Steroids

The assignment questions from yesterday's combinatorics module completely fried my brain. But there is no rest on the weekends if you want to clear technical rounds. Today, the curriculum shifted from abstract recursion into a formal algorithm design paradigm: Divide and Conquer.

If you've ever tried to sort a massive array using Bubble Sort or Insertion Sort, you know it's a disaster. Those algorithms take $O(N^2)$ time. If you pass them a million records, your server will freeze. Divide & Conquer fixes this by slashing the array in half, sorting the tiny pieces, and stitching them back together. The first algorithm on the list is the legendary Merge Sort.

---

🔪 The Divide and The Merge

Merge Sort is conceptually brutally simple, but coding the "Merge" step is an index-tracking nightmare.

1. The Divide Step (Trivial)

You calculate the mid point and recursively call Merge Sort on the left half and the right half. You keep slicing the array until you are left with individual chunks of size 1. A single element is technically already sorted.

2. The Merge Step (The Headache)

Now you have two sorted sub-arrays. You need to combine them into one sorted array. You use two pointers (one for each sub-array) and a temporary array. You compare the elements, pick the smaller one, shove it into the temp array, and move the pointer. Once done, you copy the temp array back into the original array.

---

💻 The C++ Implementation

This algorithm guarantees $O(N \log N)$ time complexity. But here is the brutal truth: It is a memory hog. Because we have to create that temporary array during the merge step, it takes $O(N)$ extra space. In a system with tight RAM limits, Merge Sort will crash your application.

#include <iostream>
#include <vector>
using namespace std;

// The Conquer Step
void merge(vector<int>& arr, int si, int mid, int ei) {
    vector<int> temp;
    int i = si;      // iterator for left part
    int j = mid + 1; // iterator for right part

    // Compare and push the smaller element
    while (i <= mid && j <= ei) {
        if (arr[i] < arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }

    // Push remaining elements of left part
    while (i <= mid) temp.push_back(arr[i++]);
    
    // Push remaining elements of right part
    while (j <= ei) temp.push_back(arr[j++]);

    // Copy temp array back to original array
    for (int k = 0, idx = si; k < temp.size(); k++, idx++) {
        arr[idx] = temp[k];
    }
}

// The Divide Step
void mergeSort(vector<int>& arr, int si, int ei) {
    if (si >= ei) return; // Base case

    int mid = si + (ei - si) / 2;
    mergeSort(arr, si, mid);       // Sort left
    mergeSort(arr, mid + 1, ei);   // Sort right
    merge(arr, si, mid, ei);       // Merge them
}

int main() {
    vector<int> arr = {6, 3, 9, 5, 2, 8};
    mergeSort(arr, 0, arr.size() - 1);
    
    cout << "Sorted Array: ";
    for(int val : arr) cout << val << " "; 
    // Output: 2 3 5 6 8 9
    return 0;
}

---

🎯 The Next Evolution

Merge Sort is fast, but the memory overhead is unacceptable for certain systems. Tomorrow, we look at its aggressive, highly-optimized cousin: Quick Sort, which completely eliminates the need for extra memory.