Insertion Sort

Insertion sort builds a sorted portion of the list one element at a time. It works by taking the next element from the unsorted portion and inserting it into the correct position within the sorted portion. Although not optimal for large datasets, it mirrors the way people often sort items by hand (like playing cards).

Example Walk-through

Let’s take this array:

[12, 11, 13, 5, 6]

Insertion sort grows a sorted section on the left by repeatedly placing the next element into its correct position.

Pass 1 - element at index 1 (11)

Sorted portion: [12] Take 11 → compare with 12 → shift 12 right → insert 11.

Result: [11, 12, 13, 5, 6]

Pass 2 - element at index 2 (13)

Sorted portion: [11, 12] 13 is already greater than all elements → stays in place.

Result: [11, 12, 13, 5, 6]

Pass 3 - element at index 3 (5)

Sorted portion: [11, 12, 13] Shift 13, 12, 11 to the right, then insert 5.

Result: [5, 11, 12, 13, 6]

Pass 4 - element at index 4 (6)

Sorted portion: [5, 11, 12, 13] Shift 11 right → insert 6 between 5 and 11.

Final result: [5, 6, 11, 12, 13]

Insertion sort’s strength is visible here: it performs very efficiently on nearly sorted inputs because fewer shifts are needed.

Rust Implementation

Here is an idiomatic, in-place insertion sort. It shifts elements to make space for inserting the current value into the correct position.

pub fn insertion_sort(arr: &mut [i32]) {
    let n = arr.len();

    for i in 1..n {
        let key = arr[i];
        let mut j = i;

        // Shift elements of the sorted portion to the right
        while j > 0 && arr[j - 1] > key {
            arr[j] = arr[j - 1];
            j -= 1;
        }

        // Insert the key into its correct position
        arr[j] = key;
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_sorts() {
        let mut input = vec![12, 11, 13, 5, 6];
        insertion_sort(&mut input);
        assert_eq!(input, vec![5, 6, 11, 12, 13]);
    }
}

Example Usage

fn main() {
    let mut values = vec![9, 5, 1, 4, 3];
    insertion_sort(&mut values);
    println!("{:?}", values); // [1, 3, 4, 5, 9]
}

Time and Space Complexity

Insertion sort performs very well when the list is almost sorted, but poorly when the list is reversed.

Space Complexity

Playground Links

Rust - Insertion Sort