Insertion Sort Algorithm in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Insertion Sort on a small array

What is the output of the following C# code after sorting the array using insertion sort?

DSA C#

int[] arr = {5, 3, 8, 6, 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;
}
Console.WriteLine(string.Join(", ", arr));

A 2, 3, 5, 6, 8

B 5, 3, 8, 6, 2

C 8, 6, 5, 3, 2

D 2, 5, 3, 6, 8

💡 Hint

Insertion sort places each element in its correct position by shifting larger elements to the right.

Insertion sort iterates from the second element, placing it in the correct position among the sorted elements to its left. After processing all elements, the array is sorted in ascending order.

🧠 Conceptual

intermediate

Insertion Sort Best Case Time Complexity

What is the best case time complexity of insertion sort and when does it occur?

A O(n), when the array is already sorted

B O(log n), when the array has few unique elements

C O(n^2), when the array is sorted in reverse order

D O(n log n), when the array is randomly ordered

💡 Hint

Think about how many shifts happen if the array is already sorted.

In the best case, insertion sort only compares each element once because all elements are already in order, resulting in O(n) time complexity.

🔧 Debug

advanced

Identify the bug in this insertion sort code

What error will occur when running this insertion sort code snippet?

DSA C#

int[] arr = {4, 2, 7};
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;
}

A NullReferenceException

B No error, code runs correctly

C IndexOutOfRangeException

D SyntaxError

💡 Hint

Check the loop condition and array indexing carefully.

The loop uses i <= arr.Length which causes i to reach arr.Length, an invalid index, causing IndexOutOfRangeException.

🚀 Application

advanced

Insertion Sort on Linked List

Which of the following statements about applying insertion sort on a singly linked list is true?

A Insertion sort is not possible on linked lists

B Insertion sort can be done efficiently by rearranging node pointers without extra space

C Insertion sort on linked lists always requires O(n^3) time

D Insertion sort requires converting the linked list to an array first

💡 Hint

Think about how nodes can be moved by changing links.

Insertion sort on linked lists can be done by changing pointers to insert nodes in the correct position, without extra arrays or space.

❓ Predict Output

expert

Output after partial insertion sort steps

Given the array and partial insertion sort steps below, what is the array state after the second iteration (i=2)?

DSA C#

int[] arr = {9, 4, 7, 3};
for (int i = 1; i <= 2; 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;
}
Console.WriteLine(string.Join(", ", arr));

A 9, 4, 7, 3

B 4, 9, 7, 3

C 7, 4, 9, 3

D 4, 7, 9, 3

💡 Hint

Trace each iteration carefully and watch how elements shift.

After first iteration, array is [4,9,7,3]. After second iteration, 7 is inserted before 9, resulting in [4,7,9,3].

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