DEV Community

Harsh Mishra
Harsh Mishra

Posted on

Merge Sort C++: Story

#cpp #programming #algorithms

🌌 The Sundering and the Great Unification: The Merge Sort Saga

"That which is whole must first be broken,
and that which is broken must then be joined.
Only in division and reunion does true order rise."
— The Song of the Unifier

The world was once whole, but chaos ruled it. The kings and squires, pearls and shells, great and small — all stood in disarray. No hand could place them in order, for together they were a storm.

But an Oracle spoke:

“Break the world apart, until each stands alone.
Then, piece by piece, unite them again,
and in reunion, order shall be born.”

Thus began the saga of Merge Sort — the ritual of Sundering and Unification.

📜 The Scroll of Division 

#include <iostream>
#include <vector>
using namespace std;
Enter fullscreen mode Exit fullscreen mode

The scribes prepared their scrolls (iostream) and nets (vector), for they would need to shatter the world into pieces and then weave it whole again.

⚔️ The Spell of Unification 

void merge(vector<int>& arr, int left, int mid, int right) {
Enter fullscreen mode Exit fullscreen mode

The first spell was named merge. It was no small charm — its power was to reunite two halves, making them one. For only in this reunification could order arise.

    int n1 = mid - left + 1;
    int n2 = right - mid;
Enter fullscreen mode Exit fullscreen mode

The Oracle looked upon the world and saw it split into two.
The left half contained n1 warriors, the right half n2.
Two camps had formed, awaiting judgment.

    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
Enter fullscreen mode Exit fullscreen mode

The warriors were drawn into two scrolls: L and R. Each remembered their lineage, each carried the memory of their half. Now they stood apart, waiting to be joined again.

🌌 The Great Joining 

    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++;
    }
Enter fullscreen mode Exit fullscreen mode

The Oracle began the joining. From each side, the smallest warrior was chosen.

If the left warrior was smaller or equal, he stepped into the great line. Otherwise, the right warrior claimed the place. One by one, they marched, filling the array with order.

This was no duel — it was a dance of balance, where neither side was ignored, and each gave way when the other was smaller.

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
Enter fullscreen mode Exit fullscreen mode

When one camp was exhausted, the survivors of the other marched forth unopposed. All found their place in the new, ordered line. The merge was complete.

🏹 The Sundering Ritual 

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

The second spell was named mergeSort. Its power was the Sundering.

The Oracle gazed upon the line. If more than one soul stood within, she split it. The midpoint was chosen — dividing the realm into left and right.

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
Enter fullscreen mode Exit fullscreen mode

The Sundering was not done once, but again and again. Each half was broken further, split into smaller and smaller fragments — until only single warriors stood.

For a lone warrior needs no sorting. Alone, he is already in order.

        merge(arr, left, mid, right);
    }
}
Enter fullscreen mode Exit fullscreen mode

But once all were sundered, the Oracle began the opposite journey. The merging began. Two halves became one, then greater halves, until at last the entire realm was reunited — not in chaos, but in perfect ascending order.

🎺 The Trial of Eight 

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
Enter fullscreen mode Exit fullscreen mode

One day, seven warriors stood in a line: 38, 27, 43, 3, 9, 82, 10. They were mighty, but disordered.

    mergeSort(arr, 0, arr.size() - 1);
Enter fullscreen mode Exit fullscreen mode

The Oracle raised her hand. The Sundering began. Each warrior was torn from his companions until he stood alone.

Then, slowly, patiently, the reunification came. As halves became whole, the warriors marched into their destined places.

👏 The Herald’s Call 

    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
}
Enter fullscreen mode Exit fullscreen mode

At last, the Herald walked the line. One by one, the warriors were called. Their names rang not in chaos, but in order — the smallest first, the largest last.

The crowd roared. The prophecy was fulfilled. The realm was united, perfectly sorted.

🧠 Memory of the Sundering

  • mergeSort — the ritual of Sundering, breaking the world until only singles remain.
  • merge — the great Unification, joining halves by choosing the smallest each time.
  • while loops — the march of survivors into the final line.

Thus, Merge Sort is remembered as the Saga of Sundering and Unity, where division gave way to harmony. 🌌👑

Top comments (0)