Insertion Sort Algorithm: Complete Guide with Rust and Go

Insertion sort builds a sorted array one element at a time. It takes the next value from the unsorted region, shifts every larger value to the right, and inserts the value into the resulting gap.

For example, suppose the sorted prefix is:

[13, 24, 46] | [20, 52]

The next key is 20. Shift 46 and 24 right, then insert 20:

[13, 24, 46, 46, 52]
[13, 24, 24, 46, 52]
[13, 20, 24, 46, 52]

This resembles arranging playing cards in your hand: take one new card, scan backward through the cards already ordered, and insert it where it belongs.

Insertion sort has O(n²) average and worst-case time, but its best case is O(n). It is stable, in place, adaptive, and effective for small or nearly sorted inputs. Those properties make it more practically useful than its quadratic bound initially suggests.

This is the third article in the Sorting Algorithms series, following selection sort and bubble sort. The implementations below use Rust and Go.

What Is Insertion Sort?

Insertion sort divides the array into two logical regions:

sorted prefix | unsorted suffix

Initially, the first element is a sorted prefix of length one. For every remaining index i, the algorithm:

1. Saves array[i] as the current key.
2. Scans backward through the sorted prefix.
3. Shifts every value greater than key one position right.
4. Stops after finding a value less than or equal to key, or reaching index zero.
5. Places key into the open position.

After the insertion, the sorted prefix grows by one element.

Unlike selection sort, insertion sort does not scan the entire unsorted suffix to choose a minimum. Unlike bubble sort, it does not need complete left-to-right passes. Its work is concentrated around the distance each new value must travel.

Insertion Sort Algorithm

The shift-based pseudocode is:

for i from 1 to n - 1:
    key = array[i]
    j = i

    while j > 0 and array[j - 1] > key:
        array[j] = array[j - 1]
        j = j - 1

    array[j] = key

There are two important details:

• Start at index 1 because one element is already sorted by itself.
• Shift only when array[j - 1] > key, not when it is equal to the key. The strict comparison preserves stability.

Insertion Sort Dry Run

Let us sort:

[13, 46, 24, 52, 20, 9]

The vertical bar separates the sorted prefix from the unsorted suffix.

Pass 1: insert 46

The key 46 is already greater than 13, so no shift is needed.

[13, 46] | [24, 52, 20, 9]

Pass 2: insert 24

Compare 24 backward with the sorted prefix. Shift 46 right, then insert 24 after 13.

Start:  [13, 46, 24, 52, 20, 9]
Shift:  [13, 46, 46, 52, 20, 9]
Insert: [13, 24, 46, 52, 20, 9]
         sorted prefix

Pass 3: insert 52

52 is greater than the last sorted value, 46. It stays where it is.

[13, 24, 46, 52] | [20, 9]

Pass 4: insert 20

Shift 52, 46, and 24 one position right. Stop at 13 and insert 20 after it.

Start:  [13, 24, 46, 52, 20, 9]
Shift:  [13, 24, 46, 52, 52, 9]
Shift:  [13, 24, 46, 46, 52, 9]
Shift:  [13, 24, 24, 46, 52, 9]
Insert: [13, 20, 24, 46, 52, 9]

Pass 5: insert 9

9 is smaller than every value in the sorted prefix, so all five values shift right.

Start:  [13, 20, 24, 46, 52, 9]
Shift:  [13, 20, 24, 46, 52, 52]
Shift:  [13, 20, 24, 46, 46, 52]
Shift:  [13, 20, 24, 24, 46, 52]
Shift:  [13, 20, 20, 24, 46, 52]
Shift:  [13, 13, 20, 24, 46, 52]
Insert: [ 9, 13, 20, 24, 46, 52]

The complete array is now sorted:

[9, 13, 20, 24, 46, 52]

Why Insertion Sort Is Correct

The outer-loop invariant is:

Before processing index i, the prefix array[0..i] contains the original first i elements in sorted order.

We can prove correctness in three stages:

1. Initialization: Before i = 1, the prefix contains one element and is necessarily sorted.
2. Maintenance: The inner loop shifts every sorted-prefix value greater than key. Inserting key into the gap preserves all values and leaves the extended prefix sorted.
3. Termination: When i reaches n, the sorted prefix is the entire array.

Cornell University's insertion sort notes use the same contract: insert a[i] into the already sorted a[..i) so the larger prefix contains the same entries in sorted order.

The inner loop also has an invariant: the open position is at j, and every original value from j through i - 1 that is greater than the key has been shifted one position right. When the condition fails, j is exactly the valid insertion position.

Insertion Sort in Rust

This generic Rust implementation uses shifting rather than repeated adjacent swaps:

pub fn insertion_sort<T: Ord + Clone>(values: &mut [T]) {
    for i in 1..values.len() {
        let key = values[i].clone();
        let mut j = i;

        while j > 0 && values[j - 1] > key {
            values[j] = values[j - 1].clone();
            j -= 1;
        }

        values[j] = key;
    }
}

fn main() {
    let mut numbers = [13, 46, 24, 52, 20, 9];
    insertion_sort(&mut numbers);
    println!("{numbers:?}");
}

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

    #[test]
    fn sorts_integers() {
        let mut values = [13, 46, 24, 52, 20, 9];
        insertion_sort(&mut values);
        assert_eq!(values, [9, 13, 20, 24, 46, 52]);
    }

    #[test]
    fn handles_empty_and_duplicate_values() {
        let mut empty: [i32; 0] = [];
        insertion_sort(&mut empty);
        assert_eq!(empty, []);

        let mut duplicates = [4, 2, 4, 1, 2];
        insertion_sort(&mut duplicates);
        assert_eq!(duplicates, [1, 2, 2, 4, 4]);
    }
}

Why does the generic function require Clone? Rust does not allow moving a value directly out of an indexed borrowed slice. Cloning saves the key and copies shifted values safely without allocating another array. For primitive integers, cloning is a simple value copy.

An alternative generic implementation can use adjacent swap operations with only T: Ord, but shifting usually performs less assignment work than exchanging the key with every preceding value.

Insertion Sort in Go

The generic Go implementation works with the built-in ordered types:

package main

import "fmt"

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 | ~string
}

func InsertionSort[T Ordered](values []T) {
	for i := 1; i < len(values); i++ {
		key := values[i]
		j := i

		for j > 0 && values[j-1] > key {
			values[j] = values[j-1]
			j--
		}

		values[j] = key
	}
}

func main() {
	numbers := []int{13, 46, 24, 52, 20, 9}
	InsertionSort(numbers)
	fmt.Println(numbers)
}

Go's ordered primitive values can be assigned directly. The function modifies the underlying slice and requires no return value.

A table-driven test covers the important input shapes:

package main

import (
	"reflect"
	"testing"
)

func TestInsertionSort(t *testing.T) {
	tests := []struct {
		name  string
		input []int
		want  []int
	}{
		{"empty", []int{}, []int{}},
		{"one value", []int{7}, []int{7}},
		{"already sorted", []int{1, 2, 3}, []int{1, 2, 3}},
		{"reverse order", []int{3, 2, 1}, []int{1, 2, 3}},
		{"duplicates", []int{4, 2, 4, 1}, []int{1, 2, 4, 4}},
	}

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			InsertionSort(test.input)
			if !reflect.DeepEqual(test.input, test.want) {
				t.Fatalf("got %v, want %v", test.input, test.want)
			}
		})
	}
}

For production sorting of ordered values, use Rust's slice::sort or Go's official slices.Sort. The manual implementation is appropriate when studying the algorithm or when a measured small-input use case benefits from its behavior.

Insertion Sort Complexity Analysis

Insertion sort's runtime depends on how far each key must move.

Best case

For sorted input:

[1, 2, 3, 4, 5]

Every pass performs one failed > comparison and zero shifts. Across n - 1 keys, the total work is linear.

Worst case

For reverse-sorted input:

[5, 4, 3, 2, 1]

The key at index i shifts past all i earlier values. The number of shifts is:

1 + 2 + 3 + ... + (n - 1)
= n(n - 1) / 2

That gives quadratic time. The Cornell complexity analysis similarly derives O(n²) worst-case time from O(n) insertions that may each require O(n) work.

Insertion Sort and Inversions

An inversion is a pair (i, j) for which:

i < j but array[i] > array[j]

Each time insertion sort shifts a larger value right across the key, it removes one inversion. Therefore, the total number of shifts equals the number of inversions in the original input.

If the input has I inversions, shift-based insertion sort runs in:

O(n + I)

The n term accounts for visiting every key, and I accounts for the shifts. This is a more informative description than O(n²) for nearly sorted data.

Old Dominion University's insertion sort analysis connects adjacent movement with inversions and shows why the average remains quadratic.

Why Insertion Sort Is Adaptive

An adaptive algorithm benefits from existing order. Insertion sort adapts naturally because its inner loop stops as soon as the correct local position is found.

Consider:

[1, 2, 3, 5, 4, 6]

Only 4 needs to cross 5. Most passes perform no shifts, so the work is close to linear.

However, “one element is misplaced” does not always mean little work:

[2, 3, 4, 5, 6, 1]

The final 1 must move across every earlier value. Measure disorder through inversions or displacement, not through a visual impression alone.

Is Insertion Sort Stable?

Yes, this implementation is stable because it shifts only when:

previous > key

For equal-key records:

[(2, A), (1, C), (2, B)]

(1, C) moves to the front, but (2, B) stops after (2, A) because their keys are equal:

[(1, C), (2, A), (2, B)]

Their original A-before-B ordering remains intact. Changing the condition to previous >= key would move the later equal record before the earlier one and break stability.

Shifting vs Adjacent Swapping

Insertion sort is sometimes implemented by repeatedly swapping the key with its left neighbor:

while j > 0 and array[j] < array[j - 1]:
    swap array[j] and array[j - 1]
    j = j - 1

This is correct and easy to understand. The shift-based version generally moves less data:

• Adjacent swapping performs multiple assignments for each crossed value.
• Shifting copies each larger value once and writes the saved key once at the end.

Both variants have the same asymptotic time and remove the same inversions. Shifting is the conventional array implementation when assignment cost matters.

Does Binary Search Improve Insertion Sort?

The sorted prefix allows binary search to locate the insertion position in O(log n) comparisons instead of scanning backward linearly.

That creates binary insertion sort, but the complete algorithm does not become O(n log n). After locating the position, an array may still need to shift O(n) values to open a gap:

find position: O(log n)
shift values:  O(n)
repeat n times: O(n²) total movement

Binary insertion sort can help when comparisons are expensive and assignments are cheap. It may be worse for nearly sorted input because a backward linear scan would stop after one or two comparisons while binary search still performs logarithmic work.

For stability, binary search must choose an insertion point after existing equal keys.

Insertion Sort as an Online Algorithm

Insertion sort can process values as they arrive. If the first k values are already sorted, a newly received value can be inserted into that prefix without sorting it again from scratch.

That makes insertion sort an online algorithm. It can be useful for small continuously growing collections, although array insertion still requires shifting values. Larger streaming systems usually use balanced trees, heaps, or other data structures designed for repeated updates.

Common Insertion Sort Mistakes

Starting the outer loop at zero

Index zero already forms a sorted prefix. Start with i = 1.

Losing the key

Save array[i] before the first shift. Otherwise the shift overwrites it.

Using j >= 0 with unsigned indices

In languages with unsigned indices, zero cannot decrement to minus one. Test j > 0 before accessing j - 1.

Shifting smaller values

For ascending order, move values that are greater than the key. Reversing this comparison sorts in descending order.

Breaking stability

Do not shift equal values. Use strict > rather than >=.

Calling binary insertion sort O(n log n)

Binary search changes comparison count, not the quadratic worst-case array movement.

When Should You Use Insertion Sort?

Insertion sort is useful when:

• The collection is small.
• Input is already or almost sorted.
• Stability is required.
• O(1) auxiliary space is important.
• Values arrive incrementally into a small ordered collection.
• It is used as the small-partition base case inside a more advanced sorting algorithm.

Avoid using standalone insertion sort for large randomly ordered arrays. Its average-case movement remains quadratic.

Insertion Sort vs Bubble Sort vs Selection Sort

Insertion sort is generally the most useful of these three for small or nearly sorted arrays. Selection sort minimizes swaps. Bubble sort provides the clearest relationship between adjacent swaps and inversions.

Read the complete Selection Sort guide and Bubble Sort guide to compare their dry runs and Rust and Go implementations.

The Bottom Line

Insertion sort grows an ordered prefix:

save next key -> shift larger values -> insert key -> repeat

It is stable, in place, online, and adaptive. It runs in O(n) time on sorted input and O(n²) time on average and in the worst case. More precisely, its work is O(n + I), where I is the number of inversions.

The sorted-prefix invariant explains its correctness, while the inversion count explains its performance. Those two ideas are more reusable than memorizing the loops: they help you reason about many incremental and adaptive algorithms.

Continue through the Sorting Algorithms category for more step-by-step tutorials with Rust and Go implementations.