Crust of Rust: Sorting Algorithms

An in-depth exploration of implementing fundamental sorting algorithms in idiomatic Rust. This chapter walks through Rust's comparison traits (Ord, PartialOrd, Eq, PartialEq), builds a trait-based sorting interface, implements multiple algorithms ranging from naive $O(n^2)$ approaches to recursive $O(n \log n)$ quicksort, tackles low-level memory operations like in-place partitioning and slice rotation, and constructs custom instrumentation to empirically measure algorithmic complexity and wall-clock runtime.

1. Rust's Ordering Traits: Ord vs. PartialOrd

Rust separates type comparisons into two primary trait hierarchies: partial orderings and total orderings. This distinction is critical when designing sorting interfaces.

The Trait Definitions

• PartialEq<Rhs> & PartialOrd<Rhs>:

  • PartialOrd::partial_cmp returns Option<Ordering>.
  • It allows for values that cannot be meaningfully compared to one another (returning None).
  • Example: Floating-point numbers (f32, f64) implement PartialOrd, not Ord, because IEEE 754 defines NaN (Not a Number). NaN <= 1.0 is false, NaN >= 1.0 is false, and NaN == NaN is false.

• Eq & Ord:

  • Ord::cmp returns Ordering directly (Less, Equal, or Greater).
  • Requires a total order, meaning:
    1. Totality: For all $a$ and $b$, exactly one of $a < b$, $a == b$, or $a > b$ must be true.
    2. Transitivity: If $a < b$ and $b < c$, then $a < c$.
    3. Symmetry: If $a == b$, then $b == a$.

Note: Sorting algorithms designed for general-purpose slices require the elements to implement Ord. If you attempt to sort a slice of partially ordered types where comparisons can fail (e.g., slices containing NaN), elements cannot be consistently placed in a deterministic sequence without explicit fallback handling.

2. Standard Library Sorting Capabilities

The Rust standard library provides multiple methods on slices ([T]):

Stability in Sorting

A sorting algorithm is stable if two elements with equal comparison keys maintain their original relative positions after sorting.

• For primitive integers ([8, 4, 8]), stability has no observable semantic consequence.
• For structured data (e.g., sorting users by Last Name when they were already sorted by First Name), stability guarantees that users with identical last names remain sorted by first name.

3. Designing a Generic Sorter Architecture

To benchmark and compare different sorting implementations cleanly, we define a polymorphic Sorter trait.

pub trait Sorter {
    fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord;
}

Why a Method on &self Instead of an Associated/Static Function?

1. State and Configuration: Taking &self allows a struct implementing Sorter to carry configuration flags (such as toggling optimization strategies) without leaking those parameters into the function signature.
2. Ergonomics: By defining sort(&self, ...), callers can invoke the method using method-call syntax on instances:

pub struct StdSorter;

impl Sorter for StdSorter {
    fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord,
    {
        slice.sort();
    }
}

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

    #[test]
    fn std_sort_works() {
        let mut things = vec![4, 2, 3, 1];
        StdSorter.sort(&mut things);
        assert_eq!(things, &[1, 2, 3, 4]);
    }
}

Why Not Iterator<Item = &mut T>? Slicing provides random access ($O(1)$ indexing and swaps via slice::swap), which is fundamentally required for efficient in-place sorting algorithms. Streams and generic iterators do not know their exact length up-front and do not support bidirectional random access without first buffering elements into an allocating structure like a Vec<T>.

4. Naive $O(n^2)$ Sorting Algorithms

4.1 Bubble Sort

Bubble sort repeatedly walks the slice from left to right, comparing adjacent pairs and swapping them if they are out of order. This process repeats until a complete pass occurs without a single swap.

Implementation

pub struct BubbleSort;

impl Sorter for BubbleSort {
    fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord,
    {
        let mut swapped = true;
        while swapped {
            swapped = false;
            for i in 1..slice.len() {
                if slice[i - 1] > slice[i] {
                    slice.swap(i - 1, i);
                    swapped = true;
                }
            }
        }
    }
}

4.2 Selection Sort

Selection sort maintains a boundary dividing the slice into a sorted prefix and an unsorted suffix. In each iteration, it searches the unsorted suffix for the smallest element and swaps it to the front of that suffix.

Idiomatic Functional Implementation vs. Loop

Instead of tracking index counters manually, we can use Rust's iterator combinators (enumerate, min_by_key):

pub struct SelectionSort;

impl Sorter for SelectionSort {
    fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord,
    {
        for i in 0..slice.len() {
            // Find the index of the minimum element in the unsorted suffix slice[i..]
            let smallest_in_rest = slice[i..]
                .iter()
                .enumerate()
                .min_by_key(|&(_, value)| value)
                .map(|(idx, _)| i + idx)
                .expect("slice[i..] is non-empty");

            if i != smallest_in_rest {
                slice.swap(i, smallest_in_rest);
            }
        }
    }
}

Rust Lifetime Nuance in Closure Patterns: When calling .min_by_key(|&(_, value)| value), the pattern &(_, value) strips the outer reference produced by enumerate(). This avoids borrowing from a temporary reference yielded during iterator evaluation, cleanly satisfying the borrow checker.

4.3 Insertion Sort: Dumb Swapping vs. Smart Binary Search

Insertion sort splits the array into a sorted prefix and an unsorted suffix. It takes the first element from the unsorted suffix and shifts it into its correct location within the sorted prefix.

Strategy 1: Non-Smart (Linear Swapping)

Walk backwards from the unsorted element, swapping leftward until the preceding element is smaller.

Strategy 2: Smart (Binary Search + Slice Rotation)

Because the prefix 0..unsorted is already sorted, we can locate the exact target insertion index in $O(\log n)$ comparisons using slice::binary_search. Once the destination index is identified, slice::rotate_right shifts the intervening sub-slice in a single call without reallocating.

Implementation

pub struct InsertionSort {
    pub smart: bool,
}

impl Sorter for InsertionSort {
    fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord,
    {
        for unsorted in 1..slice.len() {
            if !self.smart {
                let mut i = unsorted;
                while i > 0 && slice[i - 1] > slice[i] {
                    slice.swap(i - 1, i);
                    i -= 1;
                }
            } else {
                // Find where slice[unsorted] belongs within the sorted prefix slice[..unsorted]
                let insert_at = match slice[..unsorted].binary_search(&slice[unsorted]) {
                    Ok(i) => i,
                    Err(i) => i,
                };
                // Rotate the slice segment to place slice[unsorted] at insert_at
                slice[insert_at..=unsorted].rotate_right(1);
            }
        }
    }
}

5. Efficient Sorting: In-Place QuickSort

QuickSort achieves an average-case time complexity of $O(n \log n)$ via divide-and-conquer:

1. Choose a pivot element.
2. Partition the slice such that elements $\le \text{pivot}$ are on the left and elements $> \text{pivot}$ are on the right.
3. Place the pivot at the boundary dividing the two partitions.
4. Recursively sort the sub-slices to the left and right of the pivot.

Solving Borrow Checker Conflicts with split_at_mut

Rust's borrow checker prohibits retaining a reference to the pivot while simultaneously mutating the rest of the slice. To resolve this without allocating auxiliary vectors, we use slice::split_first_mut or slice::split_at_mut.

pub struct QuickSort;

impl Sorter for QuickSort {
    fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord,
    {
        quick_sort(slice);
    }
}

fn quick_sort<T: Ord>(slice: &mut [T]) {
    match slice.len() {
        0 | 1 => return,
        2 => {
            if slice[0] > slice[1] {
                slice.swap(0, 1);
            }
            return;
        }
        _ => {}
    }

    let (pivot_slice, rest) = slice.split_at_mut(1);
    let pivot = &pivot_slice[0];

    let mut left = 0;
    let mut right = rest.len() - 1;

    while left <= right {
        if &rest[left] <= pivot {
            left += 1;
        } else if &rest[right] > pivot {
            if right == 0 {
                break;
            }
            right -= 1;
        } else {
            // rest[left] is > pivot and rest[right] is <= pivot; swap both
            rest.swap(left, right);
            left += 1;
            if right == 0 {
                break;
            }
            right -= 1;
        }
    }

    // Place the pivot at its correct sorted position (index left)
    // within the entire slice
    slice.swap(0, left);

    // Recursively sort sub-slices (excluding the pivot at index left)
    let (left_slice, right_slice) = slice.split_at_mut(left);
    quick_sort(left_slice);
    quick_sort(&mut right_slice[1..]); // Skip the pivot
}

Preventing usize Underflow Bug in Debug Mode

In Rust, unsigned integers (usize) panic on underflow in debug builds. When right reaches 0 and decrements via right -= 1, it underflows. Guarding with if right == 0 { break; } ensures safe termination across both release and debug execution profiles.

6. Algorithmic Complexity Comparison

7. Empirical Benchmarking Framework

To observe algorithmic complexity directly—independent of CPU cache effects and compiler auto-vectorization—we can construct an instrumentation wrapper that tracks the exact number of comparison operations executed during a sort.

7.1 The SortEvaluator Type

use std::cell::Cell;
use std::cmp::Ordering;
use std::rc::Rc;

#[derive(Clone)]
pub struct SortEvaluator<T> {
    pub value: T,
    pub comparisons: Rc<Cell<usize>>,
}

impl<T: PartialEq> PartialEq for SortEvaluator<T> {
    fn eq(&self, other: &Self) -> bool {
        self.comparisons.set(self.comparisons.get() + 1);
        self.value == other.value
    }
}

impl<T: Eq> Eq for SortEvaluator<T> {}

impl<T: PartialOrd> PartialOrd for SortEvaluator<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.comparisons.set(self.comparisons.get() + 1);
        self.value.partial_cmp(&other.value)
    }
}

impl<T: Ord> Ord for SortEvaluator<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.comparisons.set(self.comparisons.get() + 1);
        self.value.cmp(&other.value)
    }
}

7.2 Benchmark Driver

use rand::prelude::*;
use std::time::Instant;

fn run_benchmark<S: Sorter>(
    sorter: S,
    values: &[usize],
    counter: &Rc<Cell<usize>>,
) -> (usize, f64) {
    let mut cloned: Vec<SortEvaluator<usize>> = values
        .iter()
        .map(|&v| SortEvaluator {
            value: v,
            comparisons: Rc::clone(counter),
        })
        .collect();

    counter.set(0);
    let start = Instant::now();
    sorter.sort(&mut cloned);
    let elapsed = start.elapsed().as_secs_f64();
    let comp_count = counter.get();

    // Verification check (does not affect benchmark count)
    for i in 1..cloned.len() {
        assert!(cloned[i - 1].value <= cloned[i].value);
    }

    (comp_count, elapsed)
}

8. Empirical Results and Performance Analysis

Executing the benchmark across varied slice sizes ($n = 10, 100, 1000, 10000$) reveals distinct algorithmic trajectories:

Key Experimental Insights

1. The Insertion Sort Paradox (Comparisons vs. Memory Movement):

   • InsertionSort (Smart) drops comparison counts from $O(n^2)$ down to $O(n \log n)$ via binary search.
   • However, its wall-clock runtime remains $O(n^2)$ because slice::rotate_right must still shift elements linearly through memory.
   • Measuring only comparisons can produce a misleading picture of total execution cost when memory movement dominates.

2. Selection Sort vs. Bubble Sort:

   • Both perform $O(n^2)$ comparisons.
   • Selection sort performs at most $n$ swaps, making it substantially faster in practice than bubble sort, which performs up to $O(n^2)$ adjacent swaps.

3. QuickSort Scalability:

   • QuickSort and Rust's standard library sorting implementations dramatically outperform all $O(n^2)$ algorithms once $n \ge 100$.
   • At $n = 10,000$, quicksort executes orders of magnitude fewer operations than bubble sort.

Summary and Key Takeaways

• Total vs. Partial Orderings: Types implementing Ord form a strict total order, guaranteeing that any two values can be compared. Types like f32/f64 only implement PartialOrd due to NaN.
• Borrow-Checker-Compliant In-Place Partitioning: slice::split_at_mut and slice::split_first_mut allow mutating disjoint sub-slices simultaneously without violating Rust's aliasing guarantees.
• In-Place Shift via Rotation: slice::rotate_right enables clean, allocation-free element insertions when combined with slice::binary_search.
• Unsigned Arithmetic Bounds: Index counters using usize require explicit boundary checks (such as breaking when index == 0) to prevent underflow panics in debug builds.
• Comparisons vs. Swaps: Reducing comparison count (as in smart insertion sort) does not alter an algorithm's asymptotic complexity if the number of memory moves remains $O(n^2)$.
• Empirical Profiling with Interior Mutability: Rc<Cell<usize>> embedded inside custom wrapper types (SortEvaluator) allows transparent instrumentation of comparison operations across standard trait boundaries.