Insertion Sort Algorithm in DSA C++

Mental Model

Insertion sort builds a sorted list by taking one item at a time and placing it in the right spot among the already sorted items.

Analogy: Imagine sorting playing cards in your hand: you pick one card and insert it into the correct position among the cards you already hold sorted.

Unsorted array: [5, 3, 8, 6, 2]
Sorted part ↑
[5] 3 8 6 2

Dry Run Walkthrough

Input: array: [5, 3, 8, 6, 2]

Goal: Sort the array in ascending order using insertion sort

Step 1: Start with second element 3, compare with 5 and shift 5 right

[3, 5, 8, 6, 2]

Why: We insert 3 before 5 to keep the sorted part correct

Step 2: Move to element 8, it is already greater than 5, so no change

[3, 5, 8, 6, 2]

Why: 8 is in correct position relative to sorted part

Step 3: Take 6, compare with 8 and shift 8 right, then insert 6

[3, 5, 6, 8, 2]

Why: 6 fits between 5 and 8, so 8 moves right

Step 4: Take 2, shift 8, 6, 5, 3 right and insert 2 at start

[2, 3, 5, 6, 8]

Why: 2 is smallest, so it moves to front

Result:

Sorted array: [2, 3, 5, 6, 8]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // Insert key at correct position
    }
}

int main() {
    vector<int> arr = {5, 3, 8, 6, 2};
    insertionSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

for (int i = 1; i < n; i++) {

iterate over each element starting from second to insert it in sorted part

int key = arr[i];

store current element to insert

int j = i - 1;

start comparing with previous elements

while (j >= 0 && arr[j] > key) {

shift elements greater than key to the right

arr[j + 1] = arr[j];

move element one step right to make space

j--;

move left to continue checking

arr[j + 1] = key;

insert key at correct sorted position

Output

2 3 5 6 8 

Complexity Analysis

Time: O(n^2) because in worst case each element is compared with all previous elements

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Insertion sort is simpler but slower than efficient sorts like quicksort (O(n log n)), but better for small or nearly sorted data

Edge Cases

empty array

function returns immediately without changes

DSA C++

for (int i = 1; i < n; i++) {

array with one element

no sorting needed, array remains same

DSA C++

for (int i = 1; i < n; i++) {

array already sorted

minimal shifts, runs in O(n) time

DSA C++

while (j >= 0 && arr[j] > key) {

When to Use This Pattern

When you need to sort a small or nearly sorted list and want a simple method, reach for insertion sort because it inserts elements one by one in order.

Common Mistakes

Mistake: Not shifting elements before inserting key, causing overwriting
Fix: Shift all elements greater than key one position right before placing key

Mistake: Starting loop from index 0 instead of 1
Fix: Start from second element since first is trivially sorted

Summary

Insertion sort builds a sorted array by inserting each element into its correct place.

Use it for small or nearly sorted arrays where simplicity and low overhead matter.

The key insight is shifting larger elements right to make space for the current element.

Practice

1. What is the main idea behind the Insertion Sort algorithm?

easy

A. Divide the array into halves and sort each half recursively

B. Swap adjacent elements if they are in the wrong order repeatedly

C. Build the sorted array one element at a time by inserting elements in their correct position

D. Select the smallest element and swap it with the first unsorted element

Solution

1. Step 1: Understand the insertion process

   Insertion sort takes one element at a time and inserts it into the correct position in the already sorted part of the array.

2. Step 2: Compare with other sorting methods

   Unlike divide and conquer (merge sort) or swapping adjacent elements (bubble sort), insertion sort builds the sorted array gradually by insertion.

3. Final Answer:

   Build the sorted array one element at a time by inserting elements in their correct position -> Option C

4. Quick Check:

   Insertion sort = Insert elements correctly one by one [OK]

Hint: Insertion sort inserts elements step-by-step in order [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking it divides array like merge sort
• Assuming it swaps only smallest elements

2. Which of the following is the correct syntax for the inner loop condition in insertion sort in C++?

easy

A. for (int j = i + 1; j < n && arr[j] < key; j++)

B. for (int j = i - 1; j >= 0 && arr[j] > key; j--)

C. for (int j = 0; j < i && arr[j] < key; j++)

D. for (int j = i - 1; j >= 0 && arr[j] < key; j--)

Solution

1. Step 1: Identify the inner loop role

   The inner loop moves backward from the current element's previous index, shifting elements greater than the key to the right.

2. Step 2: Match the correct loop condition

   The loop continues while j >= 0 and arr[j] > key, decrementing j each time.

3. Final Answer:

   for (int j = i - 1; j >= 0 && arr[j] > key; j--) -> Option B

4. Quick Check:

   Inner loop moves backward while arr[j] > key [OK]

Hint: Inner loop moves backward while element is greater than key [OK]

Common Mistakes:

• Using j++ instead of j-- in inner loop
• Checking arr[j] < key instead of > key
• Starting inner loop from wrong index

3. What will be the output array after running insertion sort on arr = {4, 3, 2, 1}?

medium

A. [2, 3, 4, 1]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [1, 2, 3, 4]

Solution

1. Step 1: Trace first iteration

   Insert 3 into sorted part {4}: shift 4 right, array becomes {3,4,2,1}.

2. Step 2: Trace second iteration

   Insert 2 into {3,4}: shift 4 and 3 right, array becomes {2,3,4,1}.

3. Step 3: Trace third iteration

   Insert 1 into {2,3,4}: shift all right, array becomes {1,2,3,4}.

4. Final Answer:

   [1, 2, 3, 4] -> Option D

5. Quick Check:

   Sorted ascending = [1, 2, 3, 4] [OK]

Hint: Insertion sort sorts ascending by shifting larger elements right [OK]

Common Mistakes:

• Assuming array stays same if reversed
• Stopping after first iteration
• Not shifting all larger elements

4. Identify the error in this insertion sort snippet:

for (int i = 1; i < n; i++) {
  int key = arr[i];
  int j = i - 1;
  while (j >= 0 && arr[j] < key) {
    arr[j + 1] = arr[j];
    j--;
  }
  arr[j + 1] = key;
}

medium

A. The comparison in while should be arr[j] > key, not arr[j] < key

B. The loop should start from i = 0 instead of i = 1

C. The assignment arr[j + 1] = key should be outside the loop

D. The decrement j-- should be j++ inside the while loop

Solution

1. Step 1: Understand the while loop condition

   Insertion sort shifts elements greater than key to the right, so condition must be arr[j] > key.

2. Step 2: Identify the incorrect comparison

   Current code uses arr[j] < key, which shifts smaller elements incorrectly, breaking sorting.

3. Final Answer:

   The comparison in while should be arr[j] > key, not arr[j] < key -> Option A

4. Quick Check:

   Shift elements greater than key, so condition is arr[j] > key [OK]

Hint: While loop compares arr[j] > key to shift larger elements [OK]

Common Mistakes:

• Using wrong comparison sign in while condition
• Starting loop from wrong index
• Misplacing key assignment inside loop

5. Given an array arr = {5, 2, 9, 1, 5, 6}, how many total shifts (element moves) will insertion sort perform to sort it?

hard

A. 6

B. 7

C. 10

D. 5

Solution

1. Step 1: Insert 2 into {5}

   Shift 5 right (1 shift). Array: {2, 5, 9, 1, 5, 6}

2. Step 2: Insert 9 into {2, 5}

   No shift needed since 9 > 5 (0 shifts).

3. Step 3: Insert 1 into {2, 5, 9}

   Shift 9, 5, 2 right (3 shifts). Array: {1, 2, 5, 9, 5, 6}

4. Step 4: Insert 5 into {1, 2, 5, 9}

   Shift 9 right (1 shift, stops at 5 == 5). Array: {1, 2, 5, 5, 9, 6}

5. Step 5: Insert 6 into {1, 2, 5, 5, 9}

   Shift 9 right (1 shift). Array: {1, 2, 5, 5, 6, 9}

6. Final Answer:

   6 -> Option A

7. Quick Check:

   Total shifts = 1 + 0 + 3 + 1 + 1 = 6 [OK]

Hint: Count shifts by tracing each insertion carefully [OK]

Common Mistakes:

• Counting only swaps, not shifts
• Missing shifts for repeated elements
• Confusing key placement with shifts