All About Insertion Sort : From First Line to Final Optimization

What Is Sorting?

Sorting means arranging elements in a specific order.

Common Orders

• Ascending → 1, 2, 3, 4
• Descending → 4, 3, 2, 1
• Alphabetical → A, B, C

Why Sorting Is Important?

• Faster searching (Binary Search needs sorted data)
• Better data presentation
• Efficient processing
• Required in many algorithms

---

What Is a Sorting Algorithm?

A sorting algorithm is a step-by-step procedure used to arrange elements in a particular order.

Computers do not think like humans, so we must give them clear and logical steps.

---

Definition of Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm in which elements are sorted one by one by inserting each element into its correct position in the already sorted part of the array.

---

Why Is It Called Insertion Sort?

It is called Insertion Sort because:

• Elements are inserted at their correct position
• Larger elements are shifted, not repeatedly swapped
• The method follows the natural human way of sorting

---

Real-World Examples of Insertion Sort

a) Playing Cards Example

When we arrange playing cards in our hand:

• We keep the cards already sorted
• Pick one new card
• Compare it with existing cards
• Insert it at the correct position

This process is exactly Insertion Sort.

---

b) Arranging Books on a Shelf

Books are arranged by price:

• First book → already sorted
• New book arrives
• Compare price
• Insert it in the correct place

---

c) Classroom Marks Example

Teacher writes marks one by one:

• 45 → sorted
• 30 → inserted before 45
• 40 → inserted between 30 and 45

---

Basic Concept of Insertion Sort

• The array is divided into two parts:
  1. Sorted part
  2. Unsorted part
• The first element is always considered sorted
• One element is taken from the unsorted part
• It is compared with the sorted part
• Larger elements are shifted
• The element is inserted in the correct position

---

8. Golden Rule of Insertion Sort

A single element is always sorted.

Therefore, sorting starts from the second element.

---

9. Example Array

[7, 4, 3, 5, 1, 2]

---

10. Step-by-Step Dry Run (Most Important)

---

Step 0: Initial State

Sorted Part   : [7]
Unsorted Part : [4, 3, 5, 1, 2]

---

Step 1: Insert 4

• Compare 4 with 7
• 4 < 7 → shift 7
• Insert 4 in correct position

Array         : [4, 7, 3, 5, 1, 2]
Sorted Part   : [4, 7]
Unsorted Part : [3, 5, 1, 2]

---

Step 2: Insert 3

• Compare 3 with 7 → shift 7
• Compare 3 with 4 → shift 4
• Insert 3 in correct position

Array         : [3, 4, 7, 5, 1, 2]
Sorted Part   : [3, 4, 7]
Unsorted Part : [5, 1, 2]

---

Step 3: Insert 5

• Compare 5 with 7 → shift 7
• Compare 5 with 4 → stop
• Insert 5

Array         : [3, 4, 5, 7, 1, 2]
Sorted Part   : [3, 4, 5, 7]
Unsorted Part : [1, 2]

---

Step 4: Insert 1

• Compare 1 with all sorted elements
• Shift all elements
• Insert 1 at first position

Array         : [1, 3, 4, 5, 7, 2]
Sorted Part   : [1, 3, 4, 5, 7]
Unsorted Part : [2]

---

Step 5: Insert 2

• Compare 2 with sorted elements
• Shift larger elements
• Insert 2 after 1

Array         : [1, 2, 3, 4, 5, 7]
Sorted Part   : [1, 2, 3, 4, 5, 7]
Unsorted Part : []

---

Final Sorted Array

[1, 2, 3, 4, 5, 7]

---

Example 2

Sorted Part   : [4]
Unsorted Part : [3, 5, 1, 2]

Algorithm

1. Start from the second element of the array
2. Store the element in a variable called key
3. Compare key with elements in the sorted part
4. Shift all elements greater than key to the right
5. Insert key at its correct position
6. Repeat until the array is sorted

---

Pseudocode

for i = 1 to n-1
    key = arr[i]
    j = i - 1

    while j >= 0 and arr[j] > key
        arr[j + 1] = arr[j]
        j = j - 1

    arr[j + 1] = key

---

Insertion Sort Code

let arr = [4,5,1,3,9]
  function insertionSort(arr){
    let n = arr.length;
    for(let i=1; i < n; i++) {
      let curr = arr[i];
      let prev = i - 1;
      while(arr[prev] > curr && prev >= 0) {
        arr[prev + 1] = arr[prev];
        prev--;
      }
      arr[prev + 1] = curr;
    }
    return arr;
  }
  let result = insertionSort(arr);
  console.log("Sorted array", result);  

Edge Cases (VERY IMPORTANT)

Already Sorted Array

[1, 2, 3, 4]

• Best case
• No shifting
• Time → O(n)

---

❌ Reverse Sorted Array

[5, 4, 3, 2, 1]

• Worst case
• Maximum shifts
• Time → O(n²)

---

🔹 Single Element

[10]

• Already sorted
• No operations

---

🔹 Empty Array

[]

• No errors
• Returns empty array

---

🔹 Duplicate Elements

[3, 1, 2, 1]

• Order of duplicates preserved
• Insertion Sort is stable

---

1️⃣5️⃣ Time Complexity

Case	Reason	Complexity
Best	Already sorted	O(n)
Average	Random order	O(n²)
Worst	Reverse sorted	O(n²)

---

1️⃣6️⃣ Space Complexity

• O(1) → In-place algorithm
• No extra memory required

---

1️⃣7️⃣ Important Properties

Property	Answer
Stable	✅ Yes
In-place	✅ Yes
Comparison-based	✅ Yes
Adaptive	✅ Yes
Recursive	❌ No

---

1️⃣8️⃣ Why Insertion Sort Is Adaptive?

Because:

• It performs faster when array is partially sorted
• Fewer shifts = faster execution

---

1️⃣9️⃣ Advantages

✅ Simple to understand

✅ Easy to implement

✅ Efficient for small datasets

✅ Best for nearly sorted arrays

✅ Stable sorting algorithm

---

2️⃣0️⃣ Disadvantages

❌ Slow for large datasets

❌ O(n²) time complexity

❌ Not suitable for big data

---

2️⃣1️⃣ When to Use Insertion Sort?

✔ Small arrays

✔ Nearly sorted arrays

✔ Online sorting (data arrives one by one)

✔ When memory usage must be minimal

---

2️⃣2️⃣ Comparison with Other Algorithms

Algorithm	Best	Worst	Stable
Insertion Sort	O(n)	O(n²)	✅
Bubble Sort	O(n)	O(n²)	✅
Selection Sort	O(n²)	O(n²)	❌
Merge Sort	O(n log n)	O(n log n)	✅
Quick Sort	O(n log n)	O(n²)	❌

---

2️⃣3️⃣ Interview Key Points ⭐

• Starts from second element
• Shifts elements, not swaps
• Stable & in-place
• Best case O(n)
• Used in hybrid algorithms (like TimSort)

Time Complexity

Case	Time Complexity
Best Case	O(n)
Average Case	O(n²)
Worst Case	O(n²)

---

Space Complexity

• O(1) (In-place sorting)
• No extra memory required

---