Insertion Sort: Algorithm & Implementation

1️⃣ What is Insertion Sort?

🔹 Insertion Sort is a simple sorting algorithm that builds the sorted array one item at a time.
🔹 It compares each element with the previous ones and inserts it at the correct position.
🔹 Best suited for small or nearly sorted datasets.

✅ Time Complexity

Case	Complexity
Best Case (Already Sorted)	O(n)
Average Case	O(n²)
Worst Case (Reversed Order)	O(n²)

✅ Space Complexity

• O(1) (In-place sorting)

✅ Is it Stable?

✔ Yes (Preserves order of equal elements)

---

2️⃣ How Insertion Sort Works

🔹 The algorithm divides the array into sorted and unsorted parts.
🔹 It picks an element from the unsorted part and inserts it into the correct position in the sorted part.

Step-by-Step Example

📝 Input: [8, 4, 1, 6, 3]

Step	Key Element	Sorted Part	Unsorted Part	Action
1	4	8	4, 1, 6, 3	Move 8 right, Insert 4
2	1	4, 8	1, 6, 3	Move 8, 4 right, Insert 1
3	6	1, 4, 8	6, 3	Move 8 right, Insert 6
4	3	1, 4, 6, 8	3	Move 6, 4 right, Insert 3

🔹 Final Sorted Array: [1, 3, 4, 6, 8]

---

3️⃣ Insertion Sort Algorithm

🔹 Pseudocode

for i = 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]  // Shift element right
        j = j - 1
    arr[j + 1] = key  // Insert key at the correct position

---

4️⃣ Insertion Sort Implementation in C

#include <stdio.h>

// Function to perform Insertion Sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

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

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

🔹 Output

Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Simple & easy to implement
✔ Works well for small datasets
✔ Efficient for nearly sorted data (O(n) best case)
✔ In-place sorting (O(1) space)

❌ Disadvantages

❌ Inefficient for large datasets (O(n²) worst case)
❌ Slower than Quick Sort & Merge Sort for large inputs

---

6️⃣ When to Use Insertion Sort?

🔹 Best for small datasets (e.g., <100 elements).
🔹 Great for nearly sorted data (performs in O(n) time).
🔹 Used in real-world scenarios like card sorting or keyboard typing auto-sorting.

💡 For larger datasets, use Merge Sort or Quick Sort! 🚀