🎯 What is Insertion Sort?
Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time by inserting each element into its correct position in the already sorted part.
📌 Definition
Insertion Sort is a comparison-based algorithm in which each element is picked and inserted into its correct position in a sorted subarray.
🧠 How Insertion Sort Works
Steps:
- Start from the second element
- Compare it with elements before it
- Shift larger elements one position right
- Insert the element in correct position
- Repeat for all elements
📊 Example
Unsorted Array:
A = [12, 11, 13, 5, 6]
🔁 Step-by-step
Pass 1 (Insert 11)
Compare 11 with 12 → shift 12
[11, 12, 13, 5, 6]
Pass 2 (Insert 13)
Already in correct position
[11, 12, 13, 5, 6]
Pass 3 (Insert 5)
Shift 13, 12, 11
[5, 11, 12, 13, 6]
Pass 4 (Insert 6)
Shift 13, 12, 11
[5, 6, 11, 12, 13]
📌 Final Sorted Array
[5, 6, 11, 12, 13]
💻 Algorithm (Pseudocode)
InsertionSort(A, n)
1. for i = 1 to n-1
2. key = A[i]
3. j = i - 1
4. while j >= 0 AND A[j] > key
5. A[j + 1] = A[j]
6. j = j - 1
7. A[j + 1] = key
🐍 Python Program for Insertion Sort
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Example
arr = [12, 11, 13, 5, 6]
result = insertion_sort(arr)
print("Sorted Array:", result)
Output:
Sorted Array: [5, 6, 11, 12, 13]
⚡ Time Complexity
| Case | Complexity |
|---|---|
| Best Case | O(n) |
| Worst Case | O(n²) |
| Average Case | O(n²) |
📊 Space Complexity
- O(1) (in-place sorting)
🆚 Insertion Sort vs Other Sorting
| Feature | Insertion Sort | Bubble Sort | Selection Sort |
|---|---|---|---|
| Method | Insert element in correct position | Swap adjacent elements | Select minimum element |
| Best Case | O(n) | O(n) | O(n²) |
| Efficiency | Good for small/nearly sorted data | Poor | Poor |
| Stability | ✅ Stable | ✅ Stable | ❌ Not stable |
📌 Advantages
- Simple to implement
- Efficient for small or nearly sorted data
- Stable sorting algorithm
- Works in-place (no extra memory)
❌ Disadvantages
- Slow for large datasets
- O(n²) complexity in worst case
🧠 Real Life Example
- Arranging playing cards in hand 🃏
- Inserting a new book in a sorted bookshelf 📚
📌 Summary
- Insertion Sort builds a sorted list step by step
- Each element is inserted in correct position
- Best performance when data is already nearly sorted
- Simple but not suitable for large datasets
❓ Important Questions
Short Questions
- What is insertion sort?
- What is key element in insertion sort?
- What is best case complexity?
- Is insertion sort stable?
- Give one real-life example.
Long Questions
- Explain insertion sort with example.
- Write algorithm of insertion sort.
- Write Python program for insertion sort.
- Compare insertion sort with bubble and selection sort.
- Explain advantages and disadvantages of insertion sort.