Worstsort in Rust

Brent Yorgey shares a fun 2012 paper by Miguel A. Lerma about the worst possible¹ sorting algorithm, along with a cute Haskell implementation. The algorithm depends on a function $\left. f:{\mathbb{N}}\rightarrow{\mathbb{N}} \right.$ and runs in $\Omega\left( f(n) \right)$ time; in other words, we can take at least as long as any computable function (in fact, much much longer).

Naturally I felt compelled to write up an implementation in my new favourite language, Rust. It’s not quite as slick as the Haskell one, partly because I didn’t ‘cheat’ and use a standard library implementation of permutations and chose to follow the paper more closely in using Bubblesort rather than insertion sort, but mostly because Rust is more verbose with things like curly brackets than Haskell and doesn’t allow point-free style.

Here’s the business part of the code:

pub fn badsort<T: Ord + Clone>(k: usize, l: &mut [T]) {
    if k == 0 {
        bubblesort(l);
    } else {
        let mut p = permutations(l);
        badsort(k - 1, &mut p);
        l.clone_from_slice(&p[0]);
    }
}

pub fn worstsort<T, F>(l: &mut [T], f: F)
where
    T: Ord + Clone,
    F: FnOnce(usize) -> usize,
{
    badsort(f(l.len()), l);
}

worstsort runs in $\Omega\left( \left( n!^{(f{(n)})} \right)^{2} \right)$ time, where $n!^{(k)}$ abbreviates taking the factorial $k$ times. Pretty impressive for just 15 lines, about half of which is boilerplate!

I should probably submit this as a PR to the sorting crate…