DSA Tutorial

🃏 Think of cards: You pick one card at a time and insert it into its correct position in your already sorted hand.

🔧 How It Works

1. Start from the second element.
2. Compare it with elements before it.
3. Shift larger elements one position ahead.
4. Insert the current element at its correct position.

📌 Example

Given Array: [5, 2, 4, 6]

• 2 is less than 5 → insert before → [2, 5, 4, 6]
• 4 goes before 5 → [2, 4, 5, 6]
• 6 stays → [2, 4, 5, 6]

💻 C Code Example

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int a[] = {5, 2, 4, 6};
    int n = 4;
    insertionSort(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}
    

⏱️ Time Complexity:
Worst Case: O(n²)
Best Case: O(n) (when array is already sorted)
Average Case: O(n²)
🚀 Space: O(1) (In-place sorting)

💡 Ideal for small datasets or arrays that are already nearly sorted.