Insertion Sort(Sorting) — Data Structures

🌟 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 3

Here’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

---