Recursive Bubble Sort: Complete Guide with Rust and Go

Recursive bubble sort replaces bubble sort's outer loop with a recursive call.

Each call performs one left-to-right pass over the active prefix. That pass moves the largest active value to its final position. The function then calls itself with a prefix that is one element shorter.

pass over first n elements
largest reaches index n - 1
recursively sort first n - 1 elements

The sorting behavior is the same as iterative bubble sort. The important difference is memory: the iterative algorithm needs O(1) auxiliary space, while the recursive version can keep O(n) call frames active.

How Recursive Bubble Sort Works

For an active prefix of length n:

1. If n <= 1, return.
2. Compare adjacent values from index 0 through n - 2.
3. Swap every inverted pair.
4. The largest value in the prefix now occupies index n - 1.
5. Recursively sort the prefix of length n - 1.

An early-exit flag adds another base condition: if a complete pass makes no swaps, the active prefix—and therefore the complete array—is already sorted.

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

    swapped = false
    for i from 0 to n - 2:
        if array[i] > array[i + 1]:
            swap array[i] and array[i + 1]
            swapped = true

    if swapped:
        recursive_bubble_sort(array, n - 1)

Dry Run

Sort [5, 1, 4, 2, 8].

Call with n = 5

5 and 1 -> swap: [1, 5, 4, 2, 8]
5 and 4 -> swap: [1, 4, 5, 2, 8]
5 and 2 -> swap: [1, 4, 2, 5, 8]
5 and 8 -> keep: [1, 4, 2, 5, 8]

8 is final. Recurse with n = 4.

Call with n = 4

1 and 4 -> keep
4 and 2 -> swap: [1, 2, 4, 5, 8]
4 and 5 -> keep

5 is final. Recurse with n = 3.

Call with n = 3

1 and 2 -> keep
2 and 4 -> keep

No swap occurred, so the function stops early. The result is:

[1, 2, 4, 5, 8]

Why It Is Correct

After one pass over a prefix of length n, its largest value is at index n - 1. This follows because whenever the current larger value meets its right neighbor, it either remains on the right or swaps into that position.

Use induction on n:

1. A prefix of length zero or one is sorted.
2. Assume the recursive function sorts prefixes of length n - 1.
3. One pass fixes the largest of n values at the end.
4. The recursive call sorts the remaining n - 1 values.

The complete prefix is therefore sorted. The early-exit condition is valid because a full pass without an adjacent inversion proves the range is ordered.

Recursive Bubble Sort in Rust

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

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

    let mut swapped = false;
    for i in 0..(end - 1) {
        if values[i] > values[i + 1] {
            values.swap(i, i + 1);
            swapped = true;
        }
    }

    if swapped {
        sort_prefix(values, end - 1);
    }
}

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

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

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

The helper receives an index boundary instead of creating smaller slices. That avoids copying array elements during recursion.

Recursive Bubble 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 RecursiveBubbleSort[T Ordered](values []T) {
	sortPrefix(values, len(values))
}

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

	swapped := false
	for i := 0; i < end-1; i++ {
		if values[i] > values[i+1] {
			values[i], values[i+1] = values[i+1], values[i]
			swapped = true
		}
	}

	if swapped {
		sortPrefix(values, end-1)
	}
}

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

Complexity and Stack Space

The worst-case recurrence is:

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

Expanding it produces n + (n - 1) + ... + 1, which is O(n²). Cornell's recursion notes explain why space depends on maximum simultaneous call depth rather than the total number of calls.

Rust and Go do not guarantee tail-call optimization. Even though the recursive call is last, assume every call consumes another stack frame.

Recursive vs Iterative Bubble Sort

Recursion adds no sorting advantage here. It is valuable because it reveals a decrease-by-one structure: solve one pass, reduce the problem size, and trust the recursive call to finish the remainder.

Common Mistakes

• Recursing with the same end, which never reaches the base case.
• Comparing through index end - 1 and then reading i + 1 out of bounds.
• Recursing before the pass; the intended invariant requires fixing the largest value first.
• Forgetting to reset swapped for each call.
• Using >=, which swaps equal records and breaks stability.
• Calling the algorithm O(1) space because it modifies the array in place while ignoring its recursion stack.

The Bottom Line

Recursive bubble sort performs one bubble pass and reduces the active prefix by one. It remains stable and has the same O(n²) average and worst-case time as the iterative version, but its recursion can require O(n) stack space.

Use it to understand base cases, recursive progress, and stack analysis—not as a production sorting strategy. Continue with Recursive Insertion Sort, return to the complete Bubble Sort guide, or browse the Sorting Algorithms category.