Day 57: HTML Code (Insertion Sort & STL)

📅 Date: March 1, 2026

🧠 Mood: The Card Player 🃏

🔥 Topic: DSA Day 57: Insertion Sort & C++ STL Magic

🃏 Insertion Sort (The Playing Card Method)

Think about how you sort playing cards in your hand. You pick one card, find its correct position among the already sorted cards, and insert it there. That is exactly what Insertion Sort does.

It splits the array into two parts: a "sorted" part and an "unsorted" part. Elements from the unsorted part are picked and placed at the correct position in the sorted part.

Time Complexity: O(N²) worst case. BUT, O(N) in the best case (if already sorted). It is very fast for small arrays.

Space Complexity: O(1) - In-place sorting.

---

💻 Insertion Sort Code

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

void insertionSort(vector<int>& arr, int n) {
    for(int i = 1; i < n; i++) {
        int current = arr[i];
        int j = i - 1;
        
        // Shift elements of sorted part that are greater than 'current'
        // to one position ahead of their current position
        while(j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        // Insert the current element in its correct position
        arr[j + 1] = current;
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr, arr.size());
    
    cout << "Sorted array: ";
    for(int i : arr) cout << i << " ";
    return 0;
}

---

🪄 The Cheat Code: C++ STL Sort

In competitive programming or real-world development, NO ONE writes sorting algorithms from scratch. We use the built-in C++ Standard Template Library (STL) function. It is highly optimized (uses IntroSort, a mix of Quick, Heap, and Insertion sort) and runs in O(N log N) time.

#include <iostream>
#include <vector>
#include <algorithm> // 🚨 REQUIRED FOR sort()

using namespace std;

int main() {
    vector<int> v = {50, 20, 40, 10, 30};

    // Syntax: sort(starting_iterator, ending_iterator);
    sort(v.begin(), v.end());

    cout << "Sorted using STL: ";
    for(int i : v) cout << i << " ";
    
    return 0;
}

---

🚀 Day 57 Challenge

1. Use the STL sort() function to sort an array in Descending Order.
   Hint: You will need to use greater<int>(). Search about it!

Next Up on DSA Track: Merge Sort (The Divide & Conquer King).