Merge sort was boring until..

🔥 "Hey folks! Abhi here — and I promise, by the time you finish this blog, you won’t just remember how Merge Sort works — you’ll fall in love with it like I did. Buckle up, 'cause this is my all-time favorite algorithm and it’s about to blow your mind! 💥🧠"

Some really cool things about merge sort

1. Guess what? The legendary Sir John Von Neumann himself invented it! Yep, the same genius who gave us the von-Neumann architecture that's in all our modern computers. Talk about a brainy superstar! 🌟

2. 📦 Used in External Sorting

   Merge Sort is ideal for very large datasets that don’t fit into RAM. Why? Because it accesses data sequentially (great for disks), and allows for multi-pass sorting (used in database systems!).

   ---

   🧵 Easy to Parallelize

   Since the left and right halves are processed independently, Merge Sort is naturally parallelizable. Perfect for multi-threaded or distributed systems.

   ---

   🧮 Guaranteed O(n log n)

   Unlike QuickSort, Merge Sort never degrades to O(n²) — so it's great when you need consistent performance.

   ---

   📊 Backbone of Timsort

   Python and Java use Timsort, which is a hybrid of Merge Sort + Insertion Sort. Why? Because Merge Sort’s merging power + small-list efficiency = 🏆

   ---

   💡 Works on Linked Lists too!

   Unlike QuickSort (which struggles with linked lists due to random access), Merge Sort shines on linked lists — you can sort in O(n log n) without extra space!

   ---

   🎯 Divide and Conquer Champion

   It’s one of the cleanest examples of the divide-and-conquer paradigm — break problems down, solve each part, then merge!

Working of Merge Sort :

Remember the point

Single element is always sorted

Now , let’s dive deep into understanding the working of Merge sort with an example :

• Given array is : [5 , 8 , 2, 6, 1, 9 , 3]

Step 1 : Divide

• Array is partitioned into two halves until only a single element is remaining

• Can be easily done with the help of recursion

• we don’t actually have to partition the array itself but we’ll manage two pointers , start and end to account for the divided array !

Cool right?

Code Snippet Just for the Divide part?

void merge_sort(vector<int> &arr, int s, int e)
{
    if (s >= e)
        return;

    int mid = s + (e - s) / 2; // divide the array into two halves

    // keep on doing it until only 1 element is present
    merge_sort(arr, s, mid);
    merge_sort(arr, mid + 1, e);
}

int main()
{
    vector<int> arr{5, 8 , 2, 6, 1 , 9 , 3};

     // Maintain two pointers, s and e
    int s = 0, e = arr.size()-1; 

    merge_sort(arr, s, e);

    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Step 2 : Conquer/merge

• Now our problem is broken down as : “🗣️ Merge two sorted Arrays”

• Once we’re finished diving the array , we’ll keep on merging back (the sorted arrays we get after each step )

  

  Complete code with Merge function as well

    #include <iostream>
    #include <vector>
    using namespace std;
  
    void merge(vector<int> &arr, int s, int e)
    {
        int mid = s + (e - s) / 2;
        int size_1 = mid - s + 1;
        int size_2 = e - mid;
  
        int mainIndex = s;
  
        vector<int> left(size_1);
        vector<int> right(size_2);
  
        for (int i = 0; i < size_1; i++)
        {
            left[i] = arr[mainIndex++];
        }
  
        for (int i = 0; i < size_2; i++)
        {
            right[i] = arr[mainIndex++];
            // right.push_back(arr[mainIndex++]);
        }
  
        int i = 0, j = 0, k = s;
        while (j < size_2  && i < size_1 )
        {
            if (left[i] < right[j])
            {
                arr[k] = left[i];
  
                i++;
                k++;
            }
  
            else
            {
                arr[k] = right[j];
                j++;
                k++;
            }
        }
        while (i < size_1)
        {
            arr[k] = left[i];
            i++;
            k++;
        }
  
        while (j < size_2)
        {
            arr[k] = right[j];
            j++;
            k++;
        }
    }
  
    void merge_sort(vector<int> &arr, int s, int e)
    {
        if (s >= e)
            return;
  
        int mid = s + (e - s) / 2;
  
        // merge right part
        merge_sort(arr, s, mid);
        merge_sort(arr, mid + 1, e);
  
        merge(arr, s, e);
    }
  
    int main()
    {
        vector<int> arr{4, 3, 2, 1, 5, 0};
  
        int s = 0, e = arr.size()-1;
  
        merge_sort(arr, s, e);
  
        for (int i = 0; i < arr.size(); i++)
        {
            cout << arr[i] << " ";
        }
  
        return 0;
    }
  

  See ya folks ! will meet again with another blog , till then Stay Hungry Stay Nerdy ! 🚀