DSA Day 70: Quick Sort & The Worst-Case Trap

📅 Date: June 21, 2026

🧠 Mood: The Optimizer ⚡

🔥 Topic: DSA Day 70: Quick Sort & The Worst-Case Trap

⚡ Fixing the Memory Leak

Yesterday's Merge Sort algorithm annoyed me. Creating a temporary array at every single level of the recursion tree feels incredibly inefficient. In embedded systems or massive databases, you can't just duplicate data on a whim.

Today's algorithm, Quick Sort, fixes this. It is an "in-place" sorting algorithm, meaning it takes $O(1)$ extra space. It uses the same Divide & Conquer philosophy, but instead of merging at the end, it does the heavy lifting before the recursion by selecting a "Pivot" element.

---

🎯 The Pivot and Partition

The logic is entirely based on picking a standard (the pivot) and bullying the rest of the array into submission based on that standard.

1. The Partition Step

We usually pick the last element as the Pivot. We then iterate through the array. If an element is smaller than the pivot, we throw it to the left. If it's larger, we throw it to the right. Finally, we lock the Pivot into its exact, correct, permanent position in the array.

2. The $O(N^2)$ Trap

Here is the brutal truth interviewers will grill you on: Quick Sort is faster than Merge Sort on average, BUT its worst-case scenario is horrific. If you run Quick Sort on an array that is already sorted (ascending or descending), the pivot logic fails completely. It doesn't divide the array in half; it divides it by 1. The time complexity degrades to a catastrophic $O(N^2)$.

---

💻 The C++ Implementation

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

int partition(vector<int>& arr, int si, int ei) {
    int pivot = arr[ei]; // Choosing last element as pivot
    int i = si - 1;      // To make space for elements smaller than pivot

    for (int j = si; j < ei; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]); // Throw smaller element to the left
        }
    }
    // Lock the pivot in its correct position
    i++;
    swap(arr[i], arr[ei]);
    return i; // Return pivot index
}

void quickSort(vector<int>& arr, int si, int ei) {
    if (si >= ei) return;

    // Partition array and get pivot index
    int pIdx = partition(arr, si, ei);

    // Recursively sort left and right of the pivot
    quickSort(arr, si, pIdx - 1);
    quickSort(arr, pIdx + 1, ei);
}

int main() {
    vector<int> arr = {6, 3, 9, 8, 2, 5};
    quickSort(arr, 0, arr.size() - 1);
    
    cout << "Sorted Array: ";
    for(int val : arr) cout << val << " "; 
    return 0;
}

---

🎯 The Verdict

Quick Sort is the default sorting algorithm built into most programming languages (like C++'s std::sort) because of its memory efficiency and average-case speed. Tomorrow, we finish this module by revisiting an old enemy: The Rotated Sorted Array.