Insertion Sort Algorithm in DSA Java - Execution Trace

Concept Flow - Insertion Sort Algorithm

Start with second element i=1

↓

Compare current element with elements before it

↓

Shift elements larger than current to the right

↓

Insert current element at correct position

↓

Increment i and repeat until end of array

↓

Done

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

Execution Sample

DSA Java

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 among the previously sorted elements.

Execution Table

Step	Operation	Current Key	Compared Element	Shift?	Array State
1	Start with i=1	3	5	Yes	[5, 5, 8, 1, 2]
2	Insert key	3	-	No	[3, 5, 8, 1, 2]
3	Start with i=2	8	5	No	[3, 5, 8, 1, 2]
4	Insert key	8	-	No	[3, 5, 8, 1, 2]
5	Start with i=3	1	8	Yes	[3, 5, 8, 8, 2]
6	Shift	1	5	Yes	[3, 5, 5, 8, 2]
7	Shift	1	3	Yes	[3, 3, 5, 8, 2]
8	Insert key	1	-	No	[1, 3, 5, 8, 2]
9	Start with i=4	2	8	Yes	[1, 3, 5, 8, 8]
10	Shift	2	5	Yes	[1, 3, 5, 5, 8]
11	Shift	2	3	Yes	[1, 3, 3, 5, 8]
12	Insert key	2	-	No	[1, 2, 3, 5, 8]
13	i=5 end	-	-	-	Sorting complete

💡 i reaches array length 5, sorting finished

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
i	1	2	3	4	5	5
key	3	8	1	2	-	-
j	0	1	2	3	-	-
Array	[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 instead of swapping them directly?

We shift elements to the right to make space for the key. This keeps the sorted order intact and avoids multiple swaps. See steps 1, 5, and 9 in execution_table where shifting happens before inserting.

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

Because elements before j are already sorted and smaller or equal to key, so no more shifting is needed. This is shown in steps 3 and 11 where no shift occurs and insertion happens.

What happens when the key is already larger than the compared element?

No shifting occurs and the key stays in place. This is shown in step 3 where key=8 is compared to 5 and no shift happens.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What happens to the array?

A The element 8 is replaced by 1

B The element 8 is shifted right

C The element 8 is shifted to the left

D The element 1 is shifted right

💡 Hint

Check the 'Shift?' and 'Array State' columns at step 5 in execution_table

At which step does the key 2 get inserted into its correct position?

A Step 12

B Step 10

C Step 11

D Step 13

💡 Hint

Look for the step with 'Insert key' operation and key=2 in execution_table

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

A All would be 'Yes'

B Alternating 'Yes' and 'No'

C All would be 'No'

D Only the first step would be 'Yes'

💡 Hint

In a sorted array, no elements need shifting; check steps with 'No' shifts in execution_table

Concept Snapshot

Insertion Sort Algorithm:
- Start from second element (index 1)
- Compare key with elements before it
- Shift larger elements right
- Insert key at correct position
- Repeat until array end
- Time: O(n²), Space: O(1)

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 previous elements, shifts larger elements to the right, and inserts the key in the correct place. This repeats until the entire array is sorted. The execution table shows each step of shifting and inserting, and the variable tracker follows the key variables and array state. Key moments clarify why shifting is used instead of swapping and when the inner loop stops. The visual quiz tests understanding of array changes and insertion steps.

Practice

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

easy

A. Select the smallest element and swap it with the first unsorted element

B. Divide the array into halves and sort each half separately

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

D. Build the sorted array one element at a time by inserting elements in the correct position

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted array by taking one element at a time and placing it in the correct position among the already sorted elements.

2. Step 2: Compare with other sorting methods

   Other options describe different sorting algorithms: divide and conquer (merge sort), swapping adjacent elements (bubble sort), selecting smallest element (selection sort).

3. Final Answer:

   Build the sorted array one element at a time by inserting elements in the correct position -> Option D

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 into halves
• Mixing insertion sort with selection sort

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

easy

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

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

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

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

Solution

1. Step 1: Identify insertion sort loop start

   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 from i = 1 up to i < n (not i <= n) to avoid index out of bounds.

3. Final Answer:

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

4. Quick Check:

   Start from second element: i=1 [OK]

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

Common Mistakes:

• Starting loop at 0 instead of 1
• Using i <= n causing index errors
• Looping backwards incorrectly

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

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace insertion sort on array {4, 3, 2, 1}

   Start with second element 3: insert before 4 -> {3, 4, 2, 1}. Next 2: insert before 3 -> {2, 3, 4, 1}. Finally 1: insert before 2 -> {1, 2, 3, 4}.

2. Step 2: Confirm final sorted array

   After all insertions, the array is sorted ascending: [1, 2, 3, 4].

3. Final Answer:

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

4. Quick Check:

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

Hint: Insertion sort outputs sorted array ascending [OK]

Common Mistakes:

• Assuming array stays unchanged
• Confusing insertion sort with no sorting
• Partial sorting only

4. Consider this insertion sort code snippet in Java:

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] = key;
}

What is the error in this code?

medium

A. The assignment should be arr[j + 1] = key; instead of arr[j] = key;

B. The loop should start from i = 0 instead of 1

C. The condition in while loop should be arr[j] < key

D. The decrement j-- should be j++

Solution

1. Step 1: Analyze where key is placed after shifting

   After shifting elements greater than key to the right, key should be placed at arr[j + 1] because j was decremented one extra time.

2. Step 2: Identify incorrect assignment

   The code assigns arr[j] = key; which overwrites the wrong index. Correct is arr[j + 1] = key;.

3. Final Answer:

   The assignment should be arr[j + 1] = key; instead of arr[j] = key; -> Option A

4. Quick Check:

   Place key at arr[j+1] after shifting [OK]

Hint: Place key at arr[j+1] after shifting elements [OK]

Common Mistakes:

• Assigning key to arr[j] instead of arr[j+1]
• Starting loop at wrong index
• Wrong while condition direction

5. You have an array int[] arr = {5, 3, 8, 6, 2};. After performing insertion sort, what will be the state of the array after the third iteration of the outer loop?

hard

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

B. [3, 5, 6, 8, 2]

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

D. [2, 3, 5, 6, 8]

Solution

1. Step 1: Trace each iteration of insertion sort

   Initial array: {5, 3, 8, 6, 2}
   Iteration 1 (i=1): Insert 3 before 5 -> {3, 5, 8, 6, 2}
   Iteration 2 (i=2): Insert 8 (already in correct place) -> {3, 5, 8, 6, 2}
   Iteration 3 (i=3): Insert 6 before 8 -> {3, 5, 6, 8, 2}

2. Step 2: Confirm array state after third iteration

   After third iteration, array is [3, 5, 6, 8, 2].

3. Final Answer:

   [3, 5, 6, 8, 2] -> Option B

4. Quick Check:

   After 3rd iteration, partial sort up to index 3 [OK]

Hint: Trace each insertion step carefully [OK]

Common Mistakes:

• Assuming full sort after 3 iterations
• Not moving elements correctly
• Mixing up iteration counts