Unraveling the Power of Merge Sort with Recursion

Introduction: On my 8th day of the #100DaysofCode challenge, I embarked on a journey to explore the captivating world of sorting algorithms. Sorting lies at the heart of computer science, and it's a critical skill for any programmer. Today, I took a deep dive into the concept of Merge Sort, a classic sorting algorithm known for its efficiency and elegance. In this blog, I'll walk you through the magic of Merge Sort and provide you with C++ code examples that utilize the power of recursion.

Understanding Merge Sort: Merge Sort is a divide-and-conquer sorting algorithm that offers reliable performance and stability. The main idea behind Merge Sort is to divide an array into two halves, recursively sort these halves, and then merge them to produce a sorted result. Let's take a closer look at how Merge Sort unfolds:

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

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];

    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + i + 1];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    int n = arr.size();

    cout << "Original array: ";
    for (int num : arr)
        cout << num << " ";

    mergeSort(arr, 0, n - 1);

    cout << "\nSorted array: ";
    for (int num : arr)
        cout << num << " ";

    return 0;
}

Conclusion: Merge Sort, with its elegance and efficiency, is a testament to the power of recursive algorithms in sorting. It's not only a valuable tool for programmers but also a beautiful example of how breaking a complex problem into smaller parts can lead to an elegant solution. As you continue your coding journey, don't forget to explore other sorting algorithms like Bubble Sort, Selection Sort, and Quick Sort. Each of them has its own unique characteristics and strengths.

#Programming #SortingAlgorithms #MergeSort #Recursion #CodeNewbie 🚀