📅 Date: Jan 18, 2026
🔥 Topic: Sorting Part 3: Insertion Sort

🃏 The Logic

Think about how you sort playing cards in your hand. You pick a card and insert it into its correct position among the cards you've already sorted.

📊 Dry Run Table

Let's sort: [12, 11, 13, 5, 6]

Key Action (Shifting) Array State
11 12 is > 11, Shift 12 to right. Insert 11. [11, 12, 13, 5, 6]
13 12 is < 13. No shift needed. [11, 12, 13, 5, 6]
5 Shift 13, 12, 11. Insert 5 at start. [5, 11, 12, 13, 6]

💻 The Code (O(n²))

#include <iostream>
using namespace std;

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = 5;

    for(int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Move elements greater than key one step ahead
        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }

    for(int i=0; i<n; i++) cout << arr[i] << " ";
    return 0;
}

💭 Thoughts

Insertion sort is excellent when the array is already partially sorted. In that case, it runs super fast!