Bubble Sort Algorithm: Complete Guide with Rust and Go

Bubble sort is a comparison sorting algorithm that repeatedly checks adjacent elements and swaps them when they are in the wrong order.

Consider this input:

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

During the first left-to-right pass, 52 swaps with 20 and then with 9:

[13, 46, 24, 20, 9, 52]
                       ^ final position

The largest value has reached the end. The next pass can ignore it and work on the shorter unsorted region.

Bubble sort is rarely the best choice for large production datasets, but it is valuable for learning adjacent comparisons, stable sorting, adaptive algorithms, loop invariants, and inversions. This second article in the Sorting Algorithms series provides optimized implementations in Rust and Go, not only the textbook nested loops.

What Is Bubble Sort?

Bubble sort divides the array into an unsorted prefix and a sorted suffix:

unsorted region | sorted region

On every pass, the algorithm:

1. Starts at the beginning of the unsorted region.
2. Compares each value with its immediate right neighbor.
3. Swaps the pair if the left value is greater.
4. Continues to the current unsorted boundary.
5. Stops early if the entire pass performs no swaps.

Because the larger member of an inverted pair moves right, the largest unsorted value reaches the boundary by the end of the pass.

compare -> swap if inverted -> advance one position -> repeat

This differs from selection sort, which searches the whole unsorted region for one minimum and swaps only after completing the scan.

Optimized Bubble Sort Algorithm

The useful version of bubble sort has two optimizations:

• Shorten the inner loop after every pass because the sorted suffix is final.
• Stop when a pass makes no swaps because the remaining region is already sorted.

for end from n - 1 down to 1:
    swapped = false

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

    if swapped is false:
        break

The strict > comparison is important. Equal elements do not need to move, and leaving them untouched makes this implementation stable.

Bubble Sort Dry Run

Let us sort:

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

Pass 1

Compare every adjacent pair through the final index:

13 and 46 -> ordered, no swap
[13, 46, 24, 52, 20, 9]

46 and 24 -> swap
[13, 24, 46, 52, 20, 9]

46 and 52 -> ordered, no swap
[13, 24, 46, 52, 20, 9]

52 and 20 -> swap
[13, 24, 46, 20, 52, 9]

52 and 9 -> swap
[13, 24, 46, 20, 9, 52]

The largest value, 52, is final.

Pass 2

The inner loop stops before 52:

13 and 24 -> no swap
24 and 46 -> no swap
46 and 20 -> swap: [13, 24, 20, 46, 9, 52]
46 and 9  -> swap: [13, 24, 20, 9, 46, 52]

Now 46 is also final.

Pass 3

13 and 24 -> no swap
24 and 20 -> swap: [13, 20, 24, 9, 46, 52]
24 and 9  -> swap: [13, 20, 9, 24, 46, 52]

Pass 4

13 and 20 -> no swap
20 and 9  -> swap: [13, 9, 20, 24, 46, 52]

Pass 5

13 and 9 -> swap: [9, 13, 20, 24, 46, 52]

The result is:

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

If the algorithm ran another pass, it would make no swaps and stop. The shrinking boundary already lets it finish after the required n - 1 passes in this example.

Why Bubble Sort Is Correct

The outer-loop invariant is:

After p completed passes, the last p elements are in their final sorted positions, and every one of them is at least as large as every element to its left.

We can reason about it in three stages:

1. Initialization: Before the first pass, the sorted suffix is empty, so the invariant holds.
2. Maintenance: Adjacent comparisons move the largest value in the unsorted region to its right boundary. The sorted suffix grows by one.
3. Termination: After at most n - 1 passes, only one value remains outside the sorted suffix. It must also be in its correct position.

The Kansas State University bubble sort notes describe the same invariant: each outer iteration locks one additional element at the end while preserving the input elements.

The early-exit rule is also correct. If a complete pass sees no adjacent inverted pair, then every adjacent relationship is ordered:

array[0] <= array[1] <= ... <= array[n - 1]

The array is therefore sorted, and further passes cannot change it.

Bubble Sort in Rust

This implementation sorts any mutable slice whose elements implement Ord:

pub fn bubble_sort<T: Ord>(values: &mut [T]) {
    for end in (1..values.len()).rev() {
        let mut swapped = false;

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

        if !swapped {
            break;
        }
    }
}

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

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

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

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

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

The reversed range makes end shrink from the last index toward 1. For empty and one-element slices, 1..values.len() is empty, so the function returns without special-case indexing.

Rust's safe slice::swap operation exchanges adjacent elements without requiring them to implement Copy.

Bubble Sort in Go

The generic Go implementation supports 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 BubbleSort[T Ordered](values []T) {
	for end := len(values) - 1; end > 0; end-- {
		swapped := false

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

		if !swapped {
			break
		}
	}
}

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

The function changes the input slice in place. An empty slice sets end to -1, and the condition end > 0 immediately fails without indexing the slice.

A table-driven test covers sorted, reverse, duplicate, empty, and single-element inputs:

package main

import (
	"reflect"
	"testing"
)

func TestBubbleSort(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) {
			BubbleSort(test.input)
			if !reflect.DeepEqual(test.input, test.want) {
				t.Fatalf("got %v, want %v", test.input, test.want)
			}
		})
	}
}

For general application sorting, Go provides the optimized standard-library function slices.Sort. Implement bubble sort yourself when the algorithm is the subject of the exercise.

Bubble Sort Complexity Analysis

The early-exit optimization changes the best case, but not the average or worst case.

Without early exit, the best case would also be O(n²) because the algorithm would complete every pass despite making no swaps.

The maximum number of comparisons is:

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

The University of Toronto complexity analysis derives the same quadratic bound and explains why a no-swap pass can terminate early.

Comparisons and swaps are different

For sorted input, optimized bubble sort performs n - 1 comparisons and zero swaps.

For reverse-sorted input, every pair of elements is inverted. Bubble sort performs:

n(n - 1) / 2 comparisons
n(n - 1) / 2 swaps

That high number of writes is an important practical difference from selection sort, which makes at most n - 1 swaps.

Bubble Sort and Inversions

An inversion is a pair of indices (i, j) where:

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

For example, [3, 1, 2] contains two inversions:

(3, 1)
(3, 2)

Bubble sort swaps only adjacent inverted pairs. Each such swap removes exactly one inversion and does not create another one. Therefore:

The number of swaps performed by standard bubble sort equals the number of inversions in the input.

This explains its adaptiveness. A nearly sorted array has few inversions and requires few swaps. A reverse-sorted array has the maximum n(n - 1) / 2 inversions.

The early-exit version still may perform multiple passes for one small value near the end, because that value can move left by only one position during a left-to-right pass. Adaptiveness does not make every nearly sorted arrangement linear.

Is Bubble Sort Stable?

Yes—the standard version is stable when its condition is:

if left > right:
    swap

Suppose two records share the same key:

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

The algorithm may move (1, C) before both records, but it never swaps (2, A) with (2, B) because their keys are equal. Their relative order remains A before B:

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

Changing the condition to left >= right would allow equal records to swap and would make the algorithm unstable.

A Further Optimization: Track the Last Swap

The standard optimization shortens the boundary by exactly one after each pass. Sometimes the final swap happens much earlier.

If the last swap occurred at index k, everything after k was already ordered during that pass. The next pass only needs to scan through k.

end = n - 1

while end > 0:
    last_swap = 0

    for i from 0 to end - 1:
        if array[i] > array[i + 1]:
            swap array[i] and array[i + 1]
            last_swap = i

    end = last_swap

This can reduce comparisons on partially sorted inputs. It does not change the O(n²) average or worst-case complexity, so use the simpler early-exit version unless measurement or an exercise specifically calls for the tighter boundary.

Common Bubble Sort Mistakes

Scanning into the sorted suffix

After each pass, reduce the endpoint. Rechecking final elements adds comparisons without changing the result.

Forgetting to reset swapped

Set swapped = false at the beginning of every pass. Otherwise one earlier swap can prevent valid early termination later.

Breaking after the first ordered pair

One ordered adjacent pair does not mean the array is sorted. Stop only after a complete pass makes no swaps.

Using the wrong inner-loop boundary

Because the comparison reads array[i + 1], i must remain less than end. Using i <= end causes an out-of-bounds access.

Swapping equal elements

Use strict > rather than >= to preserve stability and avoid unnecessary writes.

Claiming every bubble sort has an O(n) best case

Only an implementation with the no-swap early-exit check has linear best-case time. The unoptimized fixed-pass version remains quadratic.

When Should You Use Bubble Sort?

Bubble sort is useful when:

• You are learning adjacent comparisons, invariants, or adaptiveness.
• The collection is tiny and code clarity matters more than performance.
• You need a stable in-place teaching implementation.
• You want to count inversions through the number of swaps for an exercise.
• Input is usually sorted and you specifically want the no-swap check as a simple verification pass.

Avoid it for large datasets and performance-sensitive application code. Its quadratic comparison count and potentially quadratic number of writes make it inferior to standard library sorting algorithms.

Bubble Sort vs Selection Sort

Choose selection sort when minimizing writes matters. Choose optimized bubble sort when stability and early recognition of sorted input matter. For large real-world inputs, choose neither—use the language's standard sorting facilities.

Read the complete Selection Sort Algorithm guide for its walkthrough and Rust and Go implementations.

The Bottom Line

Bubble sort repeatedly removes adjacent inversions:

compare neighbors -> swap if inverted -> largest reaches boundary -> repeat

The optimized algorithm is stable, in place, and adaptive. It uses O(1) auxiliary space, runs in O(n) time on already sorted input, and takes O(n²) time on average and in the worst case. Its swap count equals the input's inversion count.

Its greatest value is educational: bubble sort connects local adjacent operations to a globally sorted result. Once you understand its sorted-suffix invariant and no-swap termination rule, you can reason about more efficient adaptive sorting algorithms with greater confidence.

Continue with the complete Insertion Sort Algorithm guide, then explore the Sorting Algorithms category for more practical walkthroughs and Rust and Go implementations.