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 performing insertion sort on the array?

DSA C++

int arr[] = {4, 3, 2, 1};
int n = 4;
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;
}
for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
}

A 1 3 2 4

B 4 3 2 1

C 1 2 3 4

D 2 3 4 1

💡 Hint

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

Insertion sort iterates from the second element, shifting elements greater than the key to the right, then inserts the key. The final sorted array is 1 2 3 4.

🧠 Conceptual

intermediate

Number of comparisons in insertion sort best case

What is the number of comparisons insertion sort makes in the best case when the input array is already sorted?

A n - 1

B n * (n - 1) / 2

C n

D n * log n

💡 Hint

In the best case, the inner loop does not shift any elements.

In the best case, insertion sort only compares each element once with the previous one, resulting in n - 1 comparisons.

🔧 Debug

advanced

Identify the bug in this insertion sort implementation

What error will this code produce when run?

DSA C++

int arr[] = {5, 2, 4, 6, 1, 3};
int n = 6;
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;
}

A No error, sorts correctly

B Runtime error: array index out of bounds

C Compilation error: missing semicolon

D Logical error: array remains unsorted

💡 Hint

Check the loop boundary condition for i.

The loop runs with i <= n, which accesses arr[n], out of bounds since valid indices are 0 to n-1.

🚀 Application

advanced

Insertion sort on a linked list

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

A It can be implemented by rearranging node pointers without extra space

B It cannot be used on linked lists because they are unordered

C It requires shifting elements like in arrays, so it is inefficient

D It requires converting the list to an array first

💡 Hint

Think about how nodes can be moved by changing pointers.

Insertion sort on linked lists is efficient because nodes can be inserted by changing pointers without shifting data or extra space.

🧠 Conceptual

expert

Time complexity of insertion sort on nearly sorted data

If an array of size n is nearly sorted with only k elements out of place, what is the expected time complexity of insertion sort?

A O(k * log n)

B O(n + k^2)

C O(n log n)

D O(n * k)

💡 Hint

Insertion sort shifts elements only when needed, so fewer misplaced elements reduce work.

Insertion sort runs in O(n * k) time when only k elements are out of place, because each misplaced element may cause up to k shifts.