Insertion Sort

TL;DR Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position relative to those already sorted.

1. Algorithm Steps

1. Start from the second element (index 1), assume the first element is already sorted.
2. Store the current element as a “key”.
3. Compare the key with the elements before it.
4. Shift all larger elements one position ahead to make room for the key.
5. Insert the key at its correct position.
6. Repeat until the array is fully sorted.

2. Complexity

| Case | Time Complexity | Space | Notes |

| ------------- | --------------- | ---------- | ------------------------------------------ |

| Worst | O(n²) | O(1) | When array is reverse sorted |

| Average | O(n²) | O(1) | Random order |

| Best | O(n) | O(1) | Already sorted array (no shifting needed) |

| Stability | ✅ Stable | – | Maintains the relative order of duplicates |

3. Optimizations & Variants

• Early termination not commonly used, but could be added like in Bubble Sort if detecting already sorted subarrays.
• Binary Insertion Sort: Use binary search to find the correct position to insert the element (reduces comparisons but not shifts).
• Useful for: Small datasets, or arrays that are already nearly sorted.

4. Reference Python Implementation

def insertionSort(array):

for i in range(1, len(array)):

key = array[i]

j = i - 1

while j >= 0 and array[j] > key:

array[j + 1] = array[j]

j -= 1

array[j + 1] = key

return array

5. Practice

Prompt: Write a function that sorts an array of integers using Insertion Sort. Sample Input:

array = [8, 5, 2, 9, 5, 6, 3]

Expected Output:

[2, 3, 5, 5, 6, 8, 9]

Optimal Time & Space Complexity:

• Best: O(n) time, O(1) space

• Average/Worst: O(n²) time, O(1) space

6. When (Not) to Use Insertion Sort

• ✅ Use for small datasets, or when the array is nearly sorted.

• ✅ Great for online sorting (inserting one element at a time).

• ❌ Avoid for large datasets — too slow compared to Merge or Quick Sort.

• ❌ Not suited for parallelism.

7. Quick Self-Check

1. Why is Insertion Sort stable?

2. What is the best-case time complexity and when does it occur?

3. How does it compare to Selection Sort in terms of stability?

4. Can you optimize the search for insertion position?

8. Further Reading

• Introduction to Algorithms (CLRS), Section 2.1

• Visualgo: Insertion Sort

• GeeksforGeeks - Insertion Sort

Sort like a pro — one insert at a time. 🎯