This content originally appeared on DEV Community and was authored by Harsh Mishra
The Tale of the Chosen Pivot: The Quick Sort Saga
“A king is not crowned by chance,
but by the blade of division.
He rules only when all lesser kneel before him,
and the greater stand beyond.”
— The Law of the Pivot King
The realm of warriors was restless. Each claimed strength, each stood in chaos. Kings and squires alike jostled for place, yet no order ruled their line.
The Oracle spoke:
“Crown not all at once.
Choose one king — a pivot.
Place him upon his throne,
and let those weaker bow to his left,
while the stronger march to his right.
Repeat, until all kings are crowned.”
Thus began the saga of Quick Sort — the Ritual of the Pivot Kings.
The Scroll of Streams
#include <iostream>
#include <vector>
using namespace std;
The scribes unfurled their scrolls (iostream) and laid out the line of warriors (vector). Upon this field, the ritual would carve destiny.
The Coronation of the Pivot
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
From the far end of the line, a warrior was chosen as pivot. He was not always the strongest nor the weakest, but destiny marked him king for this round. His throne would soon be revealed.
int i = low - 1;
The ground was cleared. A marker was drawn just before the first warrior, at i. It waited for those loyal to kneel before the pivot king.
The Division of Allegiance
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
The Oracle moved down the line. Each warrior was tested against the pivot king.
If a warrior was lesser or equal, he pledged loyalty. He stepped left, joining those before, and the marker i advanced. Their positions were swapped, so loyalists formed a block of unity at the front.
Those greater than the pivot held back, waiting beyond. Thus, allegiance was drawn in the sand — the loyal left, the defiant right.
The Throne of the Pivot
swap(arr[i + 1], arr[high]);
return i + 1;
}
At last, the king claimed his throne. He was placed between the loyal and the defiant, his seat at i + 1. None could challenge him now, for all lesser stood before him, and all greater behind.
The partition was complete. One king’s place was secured forever.
The Endless Coronations
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
But one king was not enough. The Oracle commanded the ritual anew. With the pivot seated, the land was split into two realms — left and right. Each would find its own king.
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
The coronations continued, dividing again and again. Each realm was split, each chosen pivot crowned, until no fragment remained unruled. When the ritual ended, the entire kingdom was ordered — smallest at the dawn, greatest at the dusk.
The Trial of Nine
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5, 20, 3, 15};
On one day, nine warriors stood in chaos: 10, 7, 8, 9, 1, 5, 20, 3, 15. Each claimed a crown, none stood in order.
quickSort(arr, 0, arr.size() - 1);
The ritual of Quick Sort was called. Kings were chosen, pivots crowned, thrones assigned. Division spread like wildfire, but from it rose harmony.
The Herald’s Call
for (int x : arr) {
cout << x << " ";
}
cout << endl;
}
At last, the Herald strode forth. He called the warriors in their new order, weakest to strongest, and the line shimmered with balance.
The people bowed, for chaos had ended, and the Pivot Kings ruled in eternal order.
Memory of the Pivot
- partition — the crowning of a pivot king.
- loyal warriors ≤ pivot — step left, their positions swapped forward.
- greater warriors > pivot — remain on the right.
- swap(pivot, i+1) — the king takes his throne.
- quickSort left & right — the realms split, each crowning its own kings.
Thus, Quick Sort is remembered as the Tale of the Pivot Kings, where division forged a perfect realm.
This content originally appeared on DEV Community and was authored by Harsh Mishra