🌟 What Is Insertion Sort?
Insertion Sort is a simple algorithm that builds the sorted list one element at a time.
It starts from the second element and compares it backward with the elements before it, placing it in the correct spot — just like sorting cards in your hand.
It’s great for small lists or for lists that are already almost sorted.
🧩 How It Works — Step-by-Step
Let’s take an example array:
[5, 3, 4, 1, 2]Step 1: Start with the first element
- The first element (5) is considered sorted by itself.
Step 2: Take the next element (3)
- Compare 3 with 5.
- Since 3 < 5, move 5 one position to the right and insert 3 before it.
[3, 5, 4, 1, 2]Step 3: Next, take 4
- Compare 4 with 5 → 4 < 5 → shift 5 right.
- Compare 4 with 3 → 4 > 3 → stop.
- Insert 4 after 3.
[3, 4, 5, 1, 2]Step 4: Take 1
- Compare 1 with 5, 4, 3 → all are greater than 1, so shift them right.
- Insert 1 at the beginning.
[1, 3, 4, 5, 2]Step 5: Finally, take 2
- Compare 2 with 5, 4, 3 → all greater, shift them right.
- Insert 2 after 1.
[1, 2, 3, 4, 5]And now the list is sorted! 🎉
🖼️ Diagram: Insertion Sort in Action
Initial Array: [5, 3, 4, 1, 2]
Step 1: [3, 5, 4, 1, 2] → Insert 3 before 5
Step 2: [3, 4, 5, 1, 2] → Insert 4 between 3 and 5
Step 3: [1, 3, 4, 5, 2] → Insert 1 at the beginning
Step 4: [1, 2, 3, 4, 5] → Insert 2 between 1 and 3Here’s a simple visual:
Unsorted → [5, 3, 4, 1, 2]
↓
Compare and Insert 3 → [3, 5]
Compare and Insert 4 → [3, 4, 5]
Compare and Insert 1 → [1, 3, 4, 5]
Compare and Insert 2 → [1, 2, 3, 4, 5]
Sorted! ✅🧠 Real-Life Analogy
Imagine organizing a line of students by height.
You start with one student (already “sorted”).
Then each new student joins the line, and you look for where they belong — maybe between two taller ones or at the very start.
Everyone shifts slightly to make space.
That’s how Insertion Sort “inserts” each new item in order.
💡 Algorithm (Plain English)
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 larger elements
j = j - 1
arr[j + 1] = key // Place key at the right spot⏱️ Time and Space Complexity
| Case | Time Complexity |
|---|---|
| Best Case (Already Sorted) | O(n) |
| Average Case | O(n²) |
| Worst Case (Reverse Sorted) | O(n²) |
| Space Complexity | O(1) |
It’s not the fastest, but for small or nearly-sorted data, it’s very efficient and easy to code.
💪 Advantages
- Very simple and easy to understand.
- Works well for small or nearly sorted datasets.
- It’s an in-place algorithm (no extra memory needed).
- Stable sort — equal elements stay in their original order.
⚠️ Disadvantages
- Slow for large datasets (because of O(n²) time).
- Lots of shifting when elements are in reverse order.
🧩 Quick Summary
| Feature | Description |
|---|---|
| Type | Comparison-based |
| Time Complexity | O(n²) |
| Space Complexity | O(1) |
| Sorting Type | In-place |
| Stability | Stable |
| Best Used For | Small or nearly sorted data |
About the Author
