Ergonomic stooge sort implementation.

Implements 3 methods for stooge-sorting [T]/Vec<T>:

• .stooge_sort() (for Ord types)
• .stooge_sort_by() (for everything else; bring your own comparator function!)
• .stooge_sort_by_key() (also for everything else)

Add the following to your Cargo.toml,

[dependencies]
stoogesort = "0.2.0"

and import the [Stooge] extension trait.

use stoogesort::Stooge;

Usage should be identical to slice::sort(), slice::sort_by(), and .stooge_sort_by_key().

Sorting an Ord type using .stooge_sort():

use stoogesort::Stooge;
let mut nums = [3, 2, 1, -5];
nums.stooge_sort();
assert_eq!(nums, [-5, 1, 2, 3]);

Sorting a PartialOrd type using .stooge_sort_by()

use stoogesort::Stooge;
let mut floats = [0.1, 0.0, 1.0, -1.6];
floats.stooge_sort_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(floats, [-1.6, 0.0, 0.1, 1.0]);

Sorting strings tagged with numbers at the end:

use stoogesort::Stooge;
let mut s = [ "foo_1", "bar_0", "quux_2" ];
s.stooge_sort_by_key(|t| t.split('_').last().unwrap().parse::<i64>().unwrap());
assert_eq!(s, [ "bar_0", "foo_1", "quux_2" ]);

• The Rust project code and docs (license in LICENSE.rust) I blatantly plagiarized

• The pseudocode in the Wikipedia article for stooge sort

It's funny to implement slow algorithms in a "blazing-fast" language!

Also, I wanted to learn how to write a library (and one with a cromulent, natural interface), use traits, and publish to crates.io.

To my knowledge, 2 stooge sort implementations (not counting crates that promise to include stooge sort) already exist:

• stooge

• sorting_rs

At risk of sounding rude, I don't like them very much.

stooge can be forgiven here, as it was explicitly written as a learning project, but it's illustrative.

Pulled from that crate's README (in all its Rust 2015 glory):

extern crate stooge;

fn main() {
	let mut v: Vec<i32> = vec![1, 5, 4, 3];
	stooge::sort(&mut v);
	return v; // [1, 3, 4, 5]
}

The name is clever, but not particularly conducive to production use -- were this a serious project, I would have to write either stooge::sort(v) or sort(v) instead of v.sort(). It's backwards.

The sort() function is also implemented on [T: PartialOrd], which I find unsatisfying. More on that on the next subsection.

This one is theoretically is intended for 'production' use (judging by the version number), or at least for dissection. However, its interface is still... wonky.

let mut vec = vec![5,3,2,4];
sorting_rs::oddeven_sort(&mut vec);
assert_eq!(vec, &[2,3,4,5]);

There is an obvious receiver here, it should've been a method.

At the same time, it also implements these sorting algorithms on [T] where T: PartialOrd, which I'll now describe my problem with:

PartialOrd's .lt() (used by the < operator), .gt() (used by >), and its "-or-equal-to" variants are not mathematically airtight. Suppose there's an integer type, that, for some reason, has a NaN value. I'll call it NaNInt. NaN is not a number -- it is nonsense to use NaN in a comparison. Since there is at least one pair of NaNInts for which comparison is impossible or nonsensical, they form a partial order. Thus, the NaNInt type can only be PartialOrd. As such:

use std::cmp::Ordering;

let a = NaNInt::from(1);
let b = NaNInt::from(2);
let c = NaNInt::NaN;

assert_eq!(a.partial_cmp(b), Some(Ordering::Less));
assert_eq!(a.partial_cmp(c), None);
assert_eq!(c.partial_cmp(c), None);

Okay, we're good. This makes sense. Now, let's consider what happens when we use .lt() and .gt() on a NaN, keeping in mind that these methods return a [bool], not an [Option].

let a = NaNInt::from(1);
let b = NaNInt::from(2);
let c = NaNInt::NaN;

assert_eq!(c > a, false);
assert_eq!(c < a, false);
assert_eq!(b < c, false);
assert_eq!(b > c, false);
assert_eq!(c > c, false);
assert_eq!(c < c, false);

That's right! It's nonsense. A NaN is never less than or greater than anything else, including itself. This causes sorting on [T: PartialOrd] to be unspecified if it contains incomparable pairs of elements.

Indeed, this is documented (rather indirectly) in [slice::sort_by()].

The comparator function must define a total ordering for the elements in the slice. If the ordering is not total, the order of the elements is unspecified.

For this reason, the standard library instead provides 3 methods (+ variants for unstable (not that stooge sort is stable) and cached) for sorting slices. They are:

• [slice::sort()]

• [slice::sort_by()]

• [slice::sort_by_key()]

Notice the bound Ord on sort() and the distinct lack of one on sort_by(). Also notice the bound Ord on the type parameter K in sort_by_key().

The standard library is protecting you from an attempt to naively sort PartialOrds by making you gaze upon the Wrongness that is .sort_by(|a, b| a.partial_cmp(b).unwrap()) in the sort_by() example.

As such, I've taken the liberty of imitating the standard library in this library. It also makes implementation easy, since I can just copy function signatures and even the code itself at times.