INSERTION SORT ALGORITHM STEP BY STEP

INSERTION SORT ALGORITHM STEP BY STEP

🎯 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:

1. Start from the second element
2. Compare it with elements before it
3. Shift larger elements one position right
4. Insert the element in correct position
5. 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

1. What is insertion sort?
2. What is key element in insertion sort?
3. What is best case complexity?
4. Is insertion sort stable?
5. Give one real-life example.

---

Long Questions

1. Explain insertion sort with example.
2. Write algorithm of insertion sort.
3. Write Python program for insertion sort.
4. Compare insertion sort with bubble and selection sort.
5. Explain advantages and disadvantages of insertion sort.