Insertion Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Insertion Sort Algorithm

Start with second element i=1

↓

Compare current element with elements before it

↓

Shift elements greater than current to the right

↓

Insert current element at correct position

↓

Increment i

↓

Is i < array length?

No→Sorted array ready

↩Back to Compare

Insertion sort picks each element from the second position, shifts larger elements to the right, and inserts it in the correct place, repeating until the array is sorted.

Execution Sample

DSA Rust

let mut arr = [5, 3, 8, 1, 2];
for i in 1..arr.len() {
    let key = arr[i];
    let mut j = i;
    while j > 0 && arr[j - 1] > key {
        arr[j] = arr[j - 1];
        j -= 1;
    }
    arr[j] = key;
}

Sorts the array [5, 3, 8, 1, 2] using insertion sort by shifting elements and inserting the key at the right position.

Execution Table

Step	Operation	Comparison	Swap?	Array State
1	Pick key=3 at index 1	Compare 5 > 3	Yes	[5, 5, 8, 1, 2]
2	Shift 5 right	Compare done	Insert key=3 at index 0	[3, 5, 8, 1, 2]
3	Pick key=8 at index 2	Compare 5 > 8	No	[3, 5, 8, 1, 2]
4	Pick key=1 at index 3	Compare 8 > 1	Yes	[3, 5, 8, 8, 2]
5	Shift 8 right	Compare 5 > 1	Yes	[3, 5, 5, 8, 2]
6	Shift 5 right	Compare 3 > 1	Yes	[3, 3, 5, 8, 2]
7	Shift 3 right	Compare done	Insert key=1 at index 0	[1, 3, 5, 8, 2]
8	Pick key=2 at index 4	Compare 8 > 2	Yes	[1, 3, 5, 8, 8]
9	Shift 8 right	Compare 5 > 2	Yes	[1, 3, 5, 5, 8]
10	Shift 5 right	Compare 3 > 2	Yes	[1, 3, 3, 5, 8]
11	Compare done	Insert key=2 at index 1	Yes	[1, 2, 3, 5, 8]
12	i=5 equals array length	Stop	No	[1, 2, 3, 5, 8]

💡 i reaches array length 5, sorting complete

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	Final
i	1	1	1	2	3	3	3	3	4	4	4	4	5
key	N/A	3	3	8	1	1	1	1	2	2	2	2	N/A
j	N/A	1	0	2	3	2	1	0	4	3	2	1	N/A
Array	[5, 3, 8, 1, 2]	[5, 5, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 8, 8, 2]	[3, 5, 5, 8, 2]	[3, 3, 5, 8, 2]	[1, 3, 5, 8, 2]	[1, 3, 5, 8, 8]	[1, 3, 5, 5, 8]	[1, 3, 3, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we shift elements to the right instead of swapping directly?

We shift elements to the right to make space for the key without losing data. See steps 1, 4, and 8 in the execution_table where elements are moved right before inserting the key.

Why does the inner loop stop when j is 0 or arr[j-1] <= key?

Because either we reached the start of the array or found the correct position for the key. This is shown in steps 2, 7, and 11 where insertion happens after comparisons.

Why does the algorithm start from the second element (i=1)?

The first element is considered sorted by itself. We start from the second to compare and insert it properly. This is shown as the initial step in the concept_flow and execution_table step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the array state after shifting 8 right?

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

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

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

D [1, 3, 5, 8, 2]

💡 Hint

Check the 'Array State' column at step 4 in the execution_table.

At which step does the key 1 get inserted at index 0?

A Step 7

B Step 11

C Step 2

D Step 12

💡 Hint

Look for the step where 'Insert key=1 at index 0' happens in the execution_table.

If the initial array was already sorted, how would the 'Swap?' column mostly look?

A Mostly 'Yes' because elements need shifting

B Mostly 'No' because no shifting is needed

C Alternating 'Yes' and 'No'

D All 'Yes' because keys always move

💡 Hint

Refer to the 'Swap?' column in the execution_table for step 3 where no swap was needed.

Concept Snapshot

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

Full Transcript

Insertion sort works by taking each element from the second position and comparing it with elements before it. If the previous elements are larger, they are shifted one position to the right to make space. Then the key element is inserted at the correct position. This process repeats for all elements until the entire array is sorted. The algorithm starts at index 1 because the first element is already considered sorted. The shifting ensures no data is lost and the key finds its correct place. The process stops when the index reaches the array length. This method is simple but can be slow for large arrays.

Practice

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

easy

A. Divide the array into halves and sort each half recursively

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

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

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

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted list 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

   Unlike divide and conquer (merge sort) or swapping adjacent elements (bubble sort), insertion sort inserts elements directly into their correct place.

3. Final Answer:

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

4. Quick Check:

   Insertion sort = Insert elements correctly one by one [OK]

Hint: Insertion sort inserts elements into sorted part step-by-step [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking it divides array like merge sort
• Assuming it swaps only smallest elements

2. Which of the following Rust code snippets correctly starts the insertion sort outer loop?

easy

A. for i in 1..arr.len() {

B. for i in 0..arr.len() {

C. for i in (1..arr.len()).rev() {

D. for i in 0..arr.len()-1 {

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 Rust range syntax

   The range 1..arr.len() correctly iterates from index 1 to the last index (exclusive of arr.len()).

3. Final Answer:

   for i in 1..arr.len() { -> Option A

4. Quick Check:

   Start loop at 1 for insertion sort [OK]

Hint: Insertion sort outer loop starts at index 1 [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using reversed range incorrectly
• Off-by-one errors in range

3. What will be the output of the following Rust code after running insertion sort on arr = [4, 3, 1, 5]?

let mut arr = vec![4, 3, 1, 5];
for i in 1..arr.len() {
    let key = arr[i];
    let mut j = i;
    while j > 0 && arr[j - 1] > key {
        arr[j] = arr[j - 1];
        j -= 1;
    }
    arr[j] = key;
}
println!("{:?}", arr);

medium

A. [3, 4, 1, 5]

B. [4, 3, 1, 5]

C. [1, 3, 4, 5]

D. [1, 4, 3, 5]

Solution

1. Step 1: Trace first iteration (i=1)

   key=3, compare with 4; 4 > 3 so shift 4 right, insert 3 at index 0. Array: [3,4,1,5]

2. Step 2: Trace second iteration (i=2)

   key=1, compare with 4 and 3; both >1 so shift them right, insert 1 at index 0. Array: [1,3,4,5]

3. Step 3: Trace third iteration (i=3)

   key=5, compare with 4; 4 < 5 so no shift, insert 5 at index 3. Array unchanged: [1,3,4,5]

4. Final Answer:

   [1, 3, 4, 5] -> Option C

5. Quick Check:

   Sorted array after insertion sort = [1, 3, 4, 5] [OK]

Hint: Trace each key insertion step-by-step [OK]

Common Mistakes:

• Not shifting elements correctly
• Off-by-one errors in while loop
• Printing original array without sorting

4. Identify the bug in this Rust insertion sort snippet:

let mut arr = vec![2, 5, 3];
for i in 1..arr.len() {
    let key = arr[i];
    let mut j = i - 1;
    while j >= 0 && arr[j] > key {
        arr[j + 1] = arr[j];
        j -= 1;
    }
    arr[j + 1] = key;
}

medium

A. The key is not assigned correctly

B. The array is not mutable

C. The for loop range is incorrect

D. The variable j is unsigned and j >= 0 check causes infinite loop

Solution

1. Step 1: Analyze variable j type and condition

   In Rust, usize is unsigned, so j >= 0 is always true, causing infinite loop when j underflows.

2. Step 2: Understand while loop behavior

   When j reaches 0 and decrements, it wraps to a large number, so loop never ends.

3. Final Answer:

   The variable j is unsigned and j >= 0 check causes infinite loop -> Option D

4. Quick Check:

   Unsigned j with j >= 0 causes infinite loop [OK]

Hint: Unsigned index can't be checked with j >= 0 safely [OK]

Common Mistakes:

• Ignoring unsigned integer wrap-around
• Assuming j can be negative
• Not using a different loop condition

5. You want to modify insertion sort in Rust to sort a vector of tuples Vec<(i32, String)> by the integer value. Which change is needed in the comparison inside the while loop?

hard

A. Change arr[j - 1] > key to arr[j - 1].0 > key.0

B. Change arr[j - 1] > key to arr[j - 1].1 > key.1

C. No change needed, tuples compare automatically by second element

D. Change arr[j - 1] > key to arr[j - 1].1.len() > key.1.len()

Solution

1. Step 1: Understand tuple sorting by first element

   To sort by the integer part of the tuple, compare the first element (.0) of each tuple.

2. Step 2: Modify comparison in while loop

   Replace arr[j - 1] > key with arr[j - 1].0 > key.0 to compare integers correctly.

3. Final Answer:

   Change arr[j - 1] > key to arr[j - 1].0 > key.0 -> Option A

4. Quick Check:

   Compare tuple first elements for sorting [OK]

Hint: Compare tuple.0 to sort by integer part [OK]

Common Mistakes:

• Comparing string part instead of integer
• Assuming tuples compare by second element automatically
• Using length of string for comparison