Insertion Sort Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the basic idea behind the Insertion Sort algorithm?

Insertion Sort builds the final sorted list one item at a time by taking each element and inserting it into its correct position among the previously sorted elements.

beginner

What is the time complexity of Insertion Sort in the worst case?

The worst-case time complexity of Insertion Sort is O(n²), where n is the number of elements to sort. This happens when the list is sorted in reverse order.

intermediate

How does Insertion Sort behave with nearly sorted data?

Insertion Sort performs very efficiently on nearly sorted data, with a time complexity close to O(n), because fewer shifts are needed to insert elements in their correct positions.

beginner

Show the step-by-step insertion of the element 5 into the sorted list [1, 3, 7, 9] using Insertion Sort.

Step 1: Compare 5 with 9, shift 9 right.
Step 2: Compare 5 with 7, shift 7 right.
Step 3: Compare 5 with 3, stop shifting.
Step 4: Insert 5 after 3.
Resulting list: [1, 3, 5, 7, 9]

beginner

What is the space complexity of Insertion Sort?

Insertion Sort has a space complexity of O(1) because it sorts the list in place without needing extra space proportional to the input size.

What does Insertion Sort do at each step?

A Selects the smallest element and swaps it with the first

B Inserts the current element into the correct position in the sorted part

C Divides the list into two halves

D Swaps the current element with the last element

Insertion Sort takes the current element and inserts it into the correct position among the already sorted elements.

What is the best-case time complexity of Insertion Sort?

A O(n)

B O(n²)

C O(n log n)

D O(log n)

When the list is already sorted, Insertion Sort only compares each element once, resulting in O(n) time.

Which of these is true about Insertion Sort?

A It divides the list into sublists

B It requires extra memory proportional to the input size

C It always performs better than Quick Sort

D It is stable and sorts in place

Insertion Sort is stable (preserves order of equal elements) and sorts the list in place without extra memory.

In Insertion Sort, what happens when the current element is smaller than elements in the sorted part?

A Those elements are shifted right to make space

B The current element is discarded

C The list is reversed

D The current element is swapped with the first element

Elements larger than the current element are shifted right to insert the current element in the correct position.

Which scenario causes the worst-case performance for Insertion Sort?

A List contains all equal elements

B List is already sorted

C List is sorted in reverse order

D List is empty

When the list is sorted in reverse order, every element must be compared and shifted, causing O(n²) time.

Explain how Insertion Sort works step-by-step on a small list.

Think about sorting playing cards in your hand.

Describe the time and space complexity of Insertion Sort and when it performs best.

Consider how many comparisons and shifts happen depending on input order.

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