03 Insertion Sort

Like bubble and selection sort, it also partitions the array into sorted and unsorted partitions.

But it grows assorted partition from left to right. So, it grows a sorted partition from the front of the array.

ex. int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

It starts out by saying the first element is sorted.

• - so it compares 20 to 35 seems good [now: 20, 35, -15, 7, 55, 1, -22]

• - then -15 to 35 which moves and compares to -15 to 20 which is less so it moves to 1st position and saves it. [now: -15, 20, 35, 7, 55, 1, -22]

• - then 35 with 7 which moves, then 20 with 7 which moves, then 7 with -15 but since it is bigger it stay there. [now: -15, 7, 20, 35, 55, 1, -22]

• - it continues this way until it finishes comparing everything resulting [now: -22, -15, 1, 7, 20, 35, 55]

Summary

Insertion sort is a In-Place algorithm. We don’t need to create any temporary arrays, we have a few extra fields.

O(n²) time complexity - quadratic.

It is a stable algorithm

It will take 100 steps to sort 10 items, 10,000 steps to sort 100 items and 1,000,000 steps to sort 1000 items.

🧠 How Insertion Sort Works (In an Array)

Let’s say we have this array:

[8, 3, 5, 1]

We start sorting from index 1 (second item):

1. Compare 3 with 8 → 3 is smaller → move 8 to the right and insert 3 before it.

   [3, 8, 5, 1] 

2. Compare 5 with 8 → 5 is smaller → move 8 to the right
   Compare 5 with 3 → 5 is bigger → insert 5 after 3.

   [3, 5, 8, 1] 

3. Compare 1 with 8, 5, 3 → shift them all → insert 1 at start

   [1, 3, 5, 8] 

✅ Sorted!

📊 Why Use Insertion Sort?