DEV Community

Harsh Mishra
Harsh Mishra

Posted on

Insertion Sort C++: Story

#cpp #programming #algorithms

🏹 The Chronicles of the Order-Bearer: The Insertion Sort Saga

"A line is not born perfect.
It becomes perfect when each finds his rightful place among those before him."
— Song of the Order-Bearer

In the Kingdom of Lines, chaos walked proudly. Warriors stood not by skill, but by chance. A weakling might precede a champion, and a champion might be buried among squires.

The High Sage decreed:

“Each warrior shall step into the line one by one.
He shall not stand where he first lands, but where he belongs among those before him.
Thus, the line shall grow in order, piece by piece, until all stand as one.”

This ritual became known as the Insertion Sort.

📜 The Scroll of Lineage 

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

The scribes laid open the scrolls (iostream) and spread the line of warriors (vector). Upon these pages the ritual of order would be etched, so the kingdom would remember.

⚔️ The Call of the Sage 

void insertionSort(vector<int>& arr) {
Enter fullscreen mode Exit fullscreen mode

The Sage raised his staff and called the warriors into the ritual. The spell of insertionSort was named, and the line stood trembling, waiting to be set aright.

    int n = arr.size();
Enter fullscreen mode Exit fullscreen mode

The first step was to count them — all who would stand in the line. n was not just a number; it was the length of destiny, the measure of the order yet to come.

🏹 The Warrior Steps Forward 

    for (int i = 1; i < n; i++) {
Enter fullscreen mode Exit fullscreen mode

The first warrior at position 0 was left alone — for a single soul needs no order.

Then, beginning from the second (i = 1), each warrior stepped forward into the growing line. He could not stand merely where he entered. He had to find his rightful place among those who came before.

⚖️ The Choice of the Key 

        int key = arr[i];
        int j = i - 1;
Enter fullscreen mode Exit fullscreen mode

The chosen warrior was lifted from the line — called the key. He looked back to those who already stood ordered behind him. The one before him (j) was his rival, his test.

🛡️ The Trials of Comparison 

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
Enter fullscreen mode Exit fullscreen mode

The key warrior faced the champions before him. If a warrior (arr[j]) was stronger (greater) than him, that warrior stepped one place forward to make room.

The key pressed on, moving backward, testing again and again — until he found a rival no stronger than himself, or the beginning of the line.

Thus, each trial shifted others forward, like a ripple of respect, until the key’s rightful place was uncovered.

👑 The Final Placement 

        arr[j + 1] = key;
    }
}
Enter fullscreen mode Exit fullscreen mode

At last, the key settled into the place destiny had prepared for him. The line closed around him, stronger than before. Then the next warrior stepped forward, and the ritual repeated.

By the end, every soul had found his rightful place, and the line stood perfect — ordered from weakest to strongest.

🎺 The Trial of Eight 

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7, 3, 15};
Enter fullscreen mode Exit fullscreen mode

On one dawn, eight warriors entered the line: 12, 11, 13, 5, 6, 7, 3, 15. They stood in chaos, their strength unmatched to their order. The Sage prepared the ritual, and the people watched.

    insertionSort(arr);
Enter fullscreen mode Exit fullscreen mode

The ritual began. One by one, the warriors were lifted, tested, and placed. With each step, the line grew more ordered, until the disorder was driven out entirely.

👏 The Herald’s Call 

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

At last, the Herald marched down the line, calling each warrior in turn. Their names rang out in ascending order. The crowd cheered, for the line now mirrored the wisdom of the Sage.

🧠 Memory of the Ritual

  • The outer loop — each warrior stepping forward into the line.
  • The key — the chosen warrior, lifted to find his place.
  • The while loop — the backward trials, shifting stronger warriors forward.
  • The placement — the key settling where destiny decreed.

Thus, Insertion Sort is remembered as the Ritual of the Order-Bearer, where chaos gave way to harmony, one warrior at a time. 🏹👑

Top comments (0)