Question:

Consider the following Java code that implements the Insertion Sort algorithm:

public void insertionSort(int[] arr) {
    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 = j - 1;
        }
        
        arr[j + 1] = key;
    }
}

Write the step-by-step execution of the given insertionSort(int[] arr) method for the following array:

int[] arr = {8, 5, 2, 9, 5, 6, 3};

Answer:

Initially, the array is: [8, 5, 2, 9, 5, 6, 3]

Step 1: (i = 1)

• Key: 5
• j = 0, arr[j] = 8
• Since 8 > 5, arr[j + 1] = arr[j] (8)
• arr = [8, 8, 2, 9, 5, 6, 3]

Step 2: (i = 2)

• Key: 2
• j = 1, arr[j] = 8
• Since 8 > 2, arr[j + 1] = arr[j] (8)
• j = 0, arr[j] = 5
• Since 5 > 2, arr[j + 1] = arr[j] (5)
• arr = [2, 5, 8, 9, 5, 6, 3]

Step 3: (i = 3)

• Key: 9
• 9 > 8, so no swapping required
• arr = [2, 5, 8, 9, 5, 6, 3]

Step 4: (i = 4)

• Key: 5
• j = 3, arr[j] = 9
• Since 9 > 5, arr[j + 1] = arr[j] (9)
• j = 2, arr[j] = 8
• Since 8 > 5, arr[j + 1] = arr[j] (8)
• j = 1, arr[j] = 5
• Since 5 > 5 is false, exit the while loop
• arr[j + 1] = key (5)
• arr = [2, 5, 5, 8, 9, 6, 3]

Step 5: (i = 5)

• Key: 6
• j = 4, arr[j] = 9
• Since 9 > 6, arr[j + 1] = arr[j] (9)
• j = 3, arr[j] = 8
• Since 8 > 6, arr[j + 1] = arr[j] (8)
• j = 2, arr[j] = 5
• Since 5 < 6, exit the while loop
• arr[j + 1] = key (6)
• arr = [2, 5, 5, 6, 9, 6, 3]

Step 6: (i = 6)

• Key: 3
• j = 5, arr[j] = 9
• Since 9 > 3, arr[j + 1] = arr[j] (9)
• j = 4, arr[j] = 6
• Since 6 > 3, arr[j + 1] = arr[j] (6)
• j = 3, arr[j] = 6
• Since 6 > 3, arr[j + 1] = arr[j] (6)
• j = 2, arr[j] = 5
• Since 5 > 3, arr[j + 1] = arr[j] (5)
• j = 1, arr[j] = 5
• Since 5 > 3, arr[j + 1] = arr[j] (5)
• j = 0, arr[j] = 2
• Since 2 > 3 is false, exit the while loop
• arr[j + 1] = key (3)
• arr = [2, 3, 5, 6, 9, 6, 3]

After the execution of the insertionSort method, the sorted array would be: [2, 3, 5, 6, 6, 8, 9]