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