Recursive Insertion Sort: Complete Guide with Rust and Go

Recursive insertion sort reduces sorting n values to two operations:

1. Recursively sort the first n - 1 values.
2. Insert the final value into that sorted prefix.

sort first n - 1 -> insert nth value -> sorted first n

This is the recursive form of the outer loop in iterative insertion sort. It keeps insertion sort's stability and adaptive time behavior, but replaces O(1) loop state with an O(n) recursion stack.

Algorithm and Pseudocode

recursive_insertion_sort(array, n):
    if n <= 1:
        return

    recursive_insertion_sort(array, n - 1)

    key = array[n - 1]
    j = n - 1

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

    array[j] = key

The placement of the recursive call is essential. It runs before insertion so that the first n - 1 values satisfy the insertion step's precondition: they are already sorted.

Dry Run

Sort [5, 2, 4, 1].

The calls descend first:

sort 4 values
  sort 3 values
    sort 2 values
      sort 1 value -> base case

Then the calls return and insert their final keys:

n = 2, key = 2
[5, 2] -> shift 5 -> [2, 5, 4, 1]

n = 3, key = 4
[2, 5, 4] -> shift 5 -> [2, 4, 5, 1]

n = 4, key = 1
[2, 4, 5, 1] -> shift 5, 4, 2 -> [1, 2, 4, 5]

The sorted result is [1, 2, 4, 5].

Correctness by Induction

The recursive structure gives a direct proof:

1. Base case: A prefix of length zero or one is sorted.
2. Inductive hypothesis: Assume the function correctly sorts the first n - 1 values.
3. Inductive step: After the recursive call, the prefix is sorted. Shifting every value greater than the key and placing the key in the gap creates a sorted prefix of length n containing the same values.

Therefore the function sorts every finite prefix. This is decrease-and-conquer recursion: each call reduces the problem size by one rather than splitting it into multiple subproblems.

Recursive Insertion Sort in Rust

pub fn recursive_insertion_sort<T: Ord + Clone>(values: &mut [T]) {
    let len = values.len();
    sort_prefix(values, len);
}

fn sort_prefix<T: Ord + Clone>(values: &mut [T], end: usize) {
    if end <= 1 {
        return;
    }

    sort_prefix(values, end - 1);

    let key = values[end - 1].clone();
    let mut j = end - 1;

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

    values[j] = key;
}

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

    #[test]
    fn sorts_values_and_duplicates() {
        let mut values = [5, 2, 4, 1];
        recursive_insertion_sort(&mut values);
        assert_eq!(values, [1, 2, 4, 5]);

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

The generic Rust version uses Clone to save the key and shift values without unsafe moves from a borrowed slice.

Recursive Insertion Sort in Go

package main

import "fmt"

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

func RecursiveInsertionSort[T Ordered](values []T) {
	sortPrefix(values, len(values))
}

func sortPrefix[T Ordered](values []T, end int) {
	if end <= 1 {
		return
	}

	sortPrefix(values, end-1)

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

func main() {
	numbers := []int{5, 2, 4, 1}
	RecursiveInsertionSort(numbers)
	fmt.Println(numbers)
}

Complexity and Recurrence

In the worst case, inserting the final key takes O(n) work:

T(n) = T(n - 1) + O(n) = O(n²)

For sorted input, every insertion performs one comparison and no shifts:

T(n) = T(n - 1) + O(1) = O(n)

The recursive version's movement remains O(n + I), where I is the number of inversions, but it always creates O(n) call frames before returning. Williams College's recursive insertion-sort notes likewise distinguish its quadratic comparison bound from the additional runtime-stack storage.

Stability and Equal Keys

The shift condition uses strict >:

previous > key

If previous == key, insertion stops after the existing equal value. A later equal record therefore remains later. Using >= would shift existing equal values and reverse their relative order.

Recursive vs Iterative Insertion Sort

The recursive version is not tail-recursive: after the recursive call returns, it must still insert the current key. A compiler cannot simply replace this pattern with a loop through ordinary tail-call elimination.

Common Mistakes

• Inserting the key before recursively sorting the prefix.
• Recursing with end instead of end - 1.
• Forgetting to save the key before shifts overwrite its position.
• Reading values[j - 1] without first checking j > 0.
• Using >= and accidentally breaking stability.
• Reporting O(1) auxiliary space while ignoring O(n) active call frames.

When Is It Useful?

Recursive insertion sort is useful for:

• Learning induction and recursive preconditions.
• Demonstrating decrease-by-one problem reduction.
• Comparing call-stack space with iterative state.
• Small teaching examples where clarity matters more than runtime overhead.

Use iterative insertion sort for an actual small-input sorting routine. It has identical ordering behavior with less memory and call overhead.

The Bottom Line

Recursive insertion sort first solves a smaller sorting problem, then inserts one key:

sort n - 1 values -> insert final key -> sorted n values

It is stable and adaptive, with O(n) best-case and O(n²) average and worst-case time. The cost unique to the recursive form is O(n) stack space.

Continue with Quick Sort, compare this version with the complete iterative Insertion Sort guide, or browse the Sorting Algorithms category.