Insertion Sort Algorithm in DSA C# - Execution Trace

Concept Flow - Insertion Sort Algorithm

Start with second element i=1

↓

Compare current element with elements before it

↓

Shift elements greater than current to the right

↓

Insert current element at correct position

↓

Increment i

↓

i < array length?

No→Sorted array ready

↩Back to Compare

Insertion sort picks each element from the second position and inserts it into the sorted part on the left by shifting larger elements right.

Execution Sample

DSA C#

int[] arr = {5, 3, 8, 1, 2};
for (int i = 1; i < arr.Length; 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;
}

Sorts the array by inserting each element into its correct position in the sorted left part.

Execution Table

Step	Operation	Key	j	Array State	Action
1	Start i=1	3	0	[5, 3, 8, 1, 2]	Pick key=3, compare with 5
2	Shift arr[0] to arr[1]	3	-1	[5, 5, 8, 1, 2]	5 > 3, shift right
3	Insert key at arr[0]	3	-1	[3, 5, 8, 1, 2]	Insert 3 at position 0
4	Start i=2	8	1	[3, 5, 8, 1, 2]	Pick key=8, compare with 5
5	No shift needed	8	1	[3, 5, 8, 1, 2]	8 > 5, insert at position 2
6	Start i=3	1	2	[3, 5, 8, 1, 2]	Pick key=1, compare with 8
7	Shift arr[2] to arr[3]	1	1	[3, 5, 8, 8, 2]	8 > 1, shift right
8	Shift arr[1] to arr[2]	1	0	[3, 5, 5, 8, 2]	5 > 1, shift right
9	Shift arr[0] to arr[1]	1	-1	[3, 3, 5, 8, 2]	3 > 1, shift right
10	Insert key at arr[0]	1	-1	[1, 3, 5, 8, 2]	Insert 1 at position 0
11	Start i=4	2	3	[1, 3, 5, 8, 2]	Pick key=2, compare with 8
12	Shift arr[3] to arr[4]	2	2	[1, 3, 5, 8, 8]	8 > 2, shift right
13	Shift arr[2] to arr[3]	2	1	[1, 3, 5, 5, 8]	5 > 2, shift right
14	Shift arr[1] to arr[2]	2	0	[1, 3, 3, 5, 8]	3 > 2, shift right
15	Insert key at arr[1]	2	0	[1, 2, 3, 5, 8]	Insert 2 at position 1
16	End	-	-	[1, 2, 3, 5, 8]	i=5 equals array length, sorting done

💡 i reaches array length 5, loop ends, array is sorted

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 10	After Step 15	Final
i	1	1	2	3	4	5	5
key	3	3	8	8	1	2	-
j	0	0	-1	1	-1	0	-
Array	[5,3,8,1,2]	[5,3,8,1,2]	[3,5,8,1,2]	[3,5,8,1,2]	[1,3,5,8,2]	[1,2,3,5,8]	[1,2,3,5,8]

Key Moments - 3 Insights

Why do we shift elements to the right instead of swapping directly?

We shift elements one by one to make space for the key at the correct position. This is shown in steps 2, 7-9, and 12-14 where elements move right before inserting the key (steps 3, 10, 15).

Why does the inner loop stop when arr[j] <= key?

Because the left part is sorted, once we find an element not greater than key, the key belongs right after it. This is seen in step 15 where j=0, arr[0]=1 <= key=2, so the inner loop stops.

What happens when the key is already greater than the previous element?

No shifting occurs, and the key stays in place. For example, at step 5, key=8 is greater than 5, so no shift happens.

Visual Quiz - 3 Questions

Look at the execution table at step 9, what is the array state?

A [3, 3, 5, 8, 2]

B [1, 3, 5, 8, 2]

C [3, 5, 5, 8, 2]

D [5, 5, 8, 1, 2]

💡 Hint

Check the 'Array State' column at step 9 in the execution_table.

At which step does the key 1 get inserted into the array?

A Step 7

B Step 9

C Step 10

D Step 15

💡 Hint

Look for the step where 'Insert key at arr[0]' happens for key=1.

If the initial array was already sorted, how would the action column change?

A More shifting actions would appear

B No shifting actions, only insertions at the same position

C The key would always be smaller than previous elements

D The array state would change after every step

💡 Hint

Refer to steps 4 and 5 where no shifting occurs because key is greater than previous elements.

Concept Snapshot

Insertion Sort Algorithm:
- Start from second element (i=1)
- Pick key and compare with sorted left part
- Shift larger elements right
- Insert key at correct position
- Repeat until array is sorted
- Time: O(n^2), stable sort

Full Transcript

Insertion sort works by taking each element from the second position and inserting it into the sorted part on the left. It compares the key with elements before it, shifting larger elements to the right to make space. When the correct position is found, the key is inserted. This repeats until the whole array is sorted. The execution table shows each step, including key selection, shifting, and insertion, with the array state updated after each operation. Key moments clarify why shifting is needed, when the inner loop stops, and what happens if no shifting is required. The visual quiz tests understanding of array states and insertion steps. The snapshot summarizes the algorithm's flow and complexity.

Practice

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

easy

A. It builds the sorted array one element at a time by inserting elements in their correct position.

B. It divides the array into halves and sorts each half recursively.

C. It repeatedly swaps adjacent elements if they are in the wrong order.

D. It selects the smallest element and swaps it with the first unsorted element.

Solution

1. Step 1: Understand insertion sort 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

   Other options describe merge sort (B), bubble sort (C), and selection sort (D), which are different algorithms.

3. Final Answer:

   It builds the sorted array one element at a time by inserting elements in their correct position. -> Option A

4. Quick Check:

   Insertion sort = Insert elements step-by-step [OK]

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

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking insertion sort divides array recursively
• Mixing up selection sort with insertion sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort in C# for an array arr of length n?

easy

A. for (int i = 0; i < n; i++)

B. for (int i = 1; i <= n; i++)

C. for (int i = n - 1; i >= 0; i--)

D. for (int i = 1; i < n; i++)

Solution

1. Step 1: Identify starting index for insertion sort

   Insertion sort starts from the second element (index 1) because the first element is considered sorted.

2. Step 2: Check loop conditions

   The loop runs while i < n to cover all elements. for (int i = 1; i < n; i++) matches this.

3. Final Answer:

   for (int i = 1; i < n; i++) -> Option D

4. Quick Check:

   Start from 1 to n-1 for insertion sort loop [OK]

Hint: Start outer loop at 1, not 0, for insertion sort [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using <= n instead of < n causing out-of-bounds
• Counting backwards incorrectly

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

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace insertion sort on given array

   Start with 4 (sorted). Insert 3 before 4 -> [3,4,2,1]. Insert 2 before 3 -> [2,3,4,1]. Insert 1 before 2 -> [1,2,3,4].

2. Step 2: Confirm final sorted array

   The array is sorted in ascending order: [1, 2, 3, 4].

3. Final Answer:

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

4. Quick Check:

   Insertion sort sorts ascending -> [1, 2, 3, 4] [OK]

Hint: Insertion sort sorts array ascending step-by-step [OK]

Common Mistakes:

• Assuming array stays unchanged
• Mixing up positions during insertion
• Stopping before fully sorting

4. Identify the error in this insertion sort code snippet:

for (int i = 1; i < arr.Length; 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 variable j should start at i - 1 instead of i + 1.

B. The while loop condition should use j < arr.Length instead of j >= 0.

C. The key should be assigned after the while loop, not before.

D. The array index arr[j + 1] causes out-of-bounds error.

Solution

1. Step 1: Check initialization of j

   In insertion sort, j starts at the element before i, so it should be i - 1, not i + 1.

2. Step 2: Verify while loop condition and shifting

   The condition j >= 0 is correct to move backwards. The shifting logic is correct if j starts properly.

3. Final Answer:

   The variable j should start at i - 1 instead of i + 1. -> Option A

4. Quick Check:

   j starts at i-1 to compare previous elements [OK]

Hint: j must start left of i to compare previous elements [OK]

Common Mistakes:

• Starting j at i+1 causing wrong comparisons
• Incorrect while loop boundary causing errors
• Misplacing key assignment inside loop

5. Given a nearly sorted array int[] arr = {1, 2, 4, 3, 5, 6}, how many element shifts will insertion sort perform to fully sort it?

hard

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Identify where shifts occur

   Only the element 3 is out of order. It needs to be inserted before 4.

2. Step 2: Count shifts to insert 3

   To insert 3, j=2 (arr[2]=4 > 3), shift arr[3]=arr[2] (1 shift), j=1 (arr[1]=2 < 3), stop. Place arr[2]=3 (not a shift).

3. Step 3: Check if other shifts occur

   No other elements need shifting. Total shifts = 1.

4. Final Answer:

   1 -> Option B

5. Quick Check:

   One shift when inserting 3 [OK]

Hint: Count only elements moved to insert out-of-place items [OK]

Common Mistakes:

• Counting swaps instead of shifts
• Ignoring that placing key is not a shift
• Assuming all elements shift