Q.Consider a list of 10 elements: Array = [7,11,3,10,17,23,1,4,21,5] Determine the partially sorted list after three complete passes of insertion sort.

Shape of question

This is a plain theory question asking for the state of an array after three passes of insertion sort.

Insertion Sort: Pass-by-Pass Execution

Insertion sort builds the sorted portion one element at a time. In pass $i$, the element at index $i$ is inserted into its correct position within the already-sorted subarray [0…i-1].

Initial array:

[7, 11, 3, 10, 17, 23, 1, 4, 21, 5]

Pass 1 (insert element at index 1, which is 11):

The first element 7 is trivially sorted. Now insert 11 into the sorted portion [7].

Since 11 > 7, it stays in place.

After Pass 1: [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]

Pass 2 (insert element at index 2, which is 3):

Insert 3 into the sorted portion [7, 11].

3 < 7, so shift 7 and 11 to the right and place 3 at index 0.

After Pass 2: [3, 7, 11, 10, 17, 23, 1, 4, 21, 5] …

Insertion sort builds the sorted portion of the array one element at a time. It picks each element in turn and inserts it into its correct position within the already-sorted portion to its left. This is fundamentally different from bubble sort or selection sort — insertion sort grows a sorted prefix.

How Insertion Sort Works

The algorithm conceptually divides the array into two parts: a sorted left portion and an unsorted right portion. Initially, the sorted portion contains just the first element (a single element is trivially sorted). In each pass, we take the next element from the unsorted portion and insert it into the correct position in the sorted portion by shifting larger elements to the right.

Pass numbering: The first pass processes the element at index 1 (the second element), the second pass processes index 2, and so on. After $n$ passes, the first $n+1$ elements are sorted among themselves.

Step-by-Step Trace

Let's trace three complete passes on Array = [7, 11, 3, 10, 17, 23, 1, 4, 21, 5].

Detailed Explanation of Each Pass

Pass 1: We consider element at index 1, which is 11. The sorted portion is [7]. Since 11 > 7, no shifting is needed; 11 remains at index 1.

Pass 2: We consider element at index 2, which is 3. The sorted portion is [7, 11]. We compare 3 with 11 — it's smaller, so 11 shifts to index 2. Then compare 3 with 7 — it's smaller, so 7 shifts to index 1. Finally, 3 is inserted at index 0.

Pass 3: We consider element at index 3, which is 10. The sorted portion is now [3, 7, 11]. We compare 10 with 11 — it's smaller, so 11 shifts to index 3. Then compare 10 with 7 — it's larger, so we stop. Insert 10 at index 2. …