Insertion Sort Algorithm in DSA Rust

Mental Model

Insertion sort builds a sorted list one item at a time by inserting each new item into its correct place.

Analogy: Imagine sorting playing cards in your hand by picking one card at a time and placing it in the right position among the cards already held.

Unsorted array:
[5, 3, 8, 4, 2]

Sorted part ↑
[5] 3 8 4 2

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Sort the array in ascending order using insertion sort

Step 1: Take element 3 and compare with 5, shift 5 right and insert 3 before it

[3, 5, 8, 4, 2]

Why: 3 is smaller than 5, so it must be placed before 5 to keep sorted order

Step 2: Take element 8, it is greater than 5, keep it in place

[3, 5, 8, 4, 2]

Why: 8 is already in correct position relative to sorted part

Step 3: Take element 4, compare with 8 and 5, shift them right and insert 4

[3, 4, 5, 8, 2]

Why: 4 is smaller than 5 and 8, so it must be inserted before them

Step 4: Take element 2, compare with 8, 5, 4, 3, shift all right and insert 2 at start

[2, 3, 4, 5, 8]

Why: 2 is smallest, so it goes to the front

Result:

Sorted array:
[2, 3, 4, 5, 8]

Annotated Code

DSA Rust

fn insertion_sort(arr: &mut [i32]) {
    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;
    }
}

fn main() {
    let mut data = [5, 3, 8, 4, 2];
    insertion_sort(&mut data);
    for val in data.iter() {
        print!("{} ", val);
    }
    println!();
}

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

iterate over each element starting from second to insert it into sorted part

let key = arr[i];

store current element to insert

let mut j = i;

start comparing from current position backwards

while j > 0 && arr[j - 1] > key {

shift elements greater than key one position right

arr[j] = arr[j - 1];

move element right to make space

j -= 1;

move backward to continue checking

arr[j] = key;

insert key at correct sorted position

Output

2 3 4 5 8 

Complexity Analysis

Time: O(n^2) because in worst case each element is compared and shifted with all previous elements

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to bubble sort, insertion sort is often faster on nearly sorted data because it stops early when elements are in order

Edge Cases

empty array

function completes immediately without changes

DSA Rust

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

array with one element

no changes needed, array is already sorted

DSA Rust

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

array already sorted

minimal shifts, algorithm runs faster

DSA Rust

while j > 0 && arr[j - 1] > key {

When to Use This Pattern

When you need to sort small or nearly sorted data efficiently with simple code, reach for insertion sort because it inserts elements one by one in order.

Common Mistakes

Mistake: Not shifting elements to the right before inserting the key, causing overwriting
Fix: Shift elements greater than key one position right before placing the key

Mistake: Starting loop from index 0 instead of 1, causing unnecessary comparisons
Fix: Start from index 1 because first element is trivially sorted

Summary

Insertion sort builds a sorted array by inserting each element into its correct position.

Use it for small or nearly sorted arrays where simple and stable sorting is needed.

The key insight is shifting larger elements right to make space for the current element.

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