---

📘 Insertion Sort

1️⃣ Introduction

Insertion Sort is a simple and efficient comparison-based sorting algorithm.

🔹 Idea

It works the same way as sorting playing cards in hand:

• Take one element at a time
• Insert it into its correct position in the already sorted part

---

2️⃣ Working Principle

• Divide array into:
  • Sorted part (initially first element)
  • Unsorted part
• Pick an element from unsorted part
• Place it in correct position in sorted part

---

3️⃣ Algorithm (Insertion Sort)

🔹 Pseudocode

InsertionSort(A, n):
   for i = 1 to n-1:
       key = A[i]
       j = i - 1

       while j >= 0 and A[j] > key:
           A[j+1] = A[j]
           j = j - 1

       A[j+1] = key

---

4️⃣ Example (Step-by-Step)

🔹 Given Array:

A = [5, 2, 4, 6, 1, 3]

---

🔹 Pass 1 (i = 1)

Insert 2 into sorted part [5]

[2, 5, 4, 6, 1, 3]

---

🔹 Pass 2 (i = 2)

Insert 4 into [2, 5]

[2, 4, 5, 6, 1, 3]

---

🔹 Pass 3 (i = 3)

Insert 6 → already correct

[2, 4, 5, 6, 1, 3]

---

🔹 Pass 4 (i = 4)

Insert 1 into sorted part

[1, 2, 4, 5, 6, 3]

---

🔹 Pass 5 (i = 5)

Insert 3

[1, 2, 3, 4, 5, 6]

✔ Final Sorted Array

---

5️⃣ Time Complexity

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

---

6️⃣ Space Complexity

• O(1) (in-place sorting)
• No extra memory required

---

7️⃣ Characteristics of Insertion Sort

✔ Simple and easy to implement
✔ Stable sorting algorithm
✔ In-place algorithm
✔ Efficient for small datasets
✔ Adaptive (works faster for nearly sorted data)

---

8️⃣ Advantages

• Good for small input sizes
• Requires less memory
• Works well for nearly sorted arrays

---

9️⃣ Disadvantages

• Inefficient for large datasets
• High time complexity (O(n²))

---

🔟 Comparison with Other Sorting Algorithms

Algorithm	Time Complexity	Use Case
Insertion Sort	O(n²)	Small data
Merge Sort	O(n log n)	Large data
Quick Sort	O(n log n)	General purpose

---

🔚 Conclusion

Insertion Sort is a simple and intuitive algorithm that is best suited for small or nearly sorted datasets.

It builds the final sorted array one element at a time by inserting elements into their correct position.

---

📌 Exam Tip

👉 Always write:

• Algorithm
• One example
• Time complexity table

---