# Worstsort in Rust

28 February 2019Brent
Yorgey shares a fun 2012 paper
by Miguel A. Lerma about the worst possible^{1} 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);
- 1, &mut p);
badsort(k .clone_from_slice(&p[0]);
l}
}
pub fn worstsort<T, F>(l: &mut [T], f: F)
where
: Ord + Clone,
T: FnOnce(usize) -> usize,
F{
.len()), l);
badsort(f(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…

non-pathological: we aren’t interested in algorithms which just loop pointlessly↩︎