Crate brainsort 

brainsort: a stable sort for keys that map to an ordered integer: numbers, strings, dates, ids. It avoids comparing keys wherever the key type allows it and does less work when the input already has structure.

let mut v = vec![3, 1, 2];
brainsort::sort(&mut v);                                 // stable, by value
assert_eq!(v, [1, 2, 3]);

struct Row { id: u64, name: String, score: f64 }
let mut rows = vec![Row { id: 2, name: "b".into(), score: 1.5 }, Row { id: 1, name: "a".into(), score: 2.5 }];
brainsort::sort_by_key(&mut rows, |r| r.id);              // by a key
brainsort::sort_by_key_ref(&mut rows, |r| r.name.as_str());   // by a borrowed key
brainsort::sort_by_key(&mut rows, |r| (r.id, brainsort::Desc(r.score)));
brainsort::sort_by(&mut rows, |a, b| a.name.cmp(&b.name));   // a comparator
assert_eq!(rows[0].name, "a");
let mut v = vec![3i64, 1, 2];
brainsort::sort_by_inferred(&mut v, |a, b| b.cmp(a));     // a comparator whose key is inferred
assert_eq!(v, [3, 2, 1]);

Every sort is stable. Keys can be any integer, bool, char, f32, f64, Duration, raw pointer, str, String, [u8], Vec<u8>, CStr, OsStr, Path and their owned forms, a tuple or array of those, or Desc for a reversed order; your own key type implements Key (see fixed_key! and bytes_key!). Elements can be anything: they are permuted once, after the keys were sorted. A comparator gets a comparison sort from sort_by, or the radix sort from sort_by_inferred when it turns out to be the order of a window of the element.

How it sorts

One pass over the keys comes first, before anything is built: it counts descents and ascents and stops as soon as they prove the input unordered. Sorted input returns at once; reversed input is reversed in place with equal keys kept in their order; nearly sorted input (at most one descent in sixteen) is fixed in place when the elements are at most 16 bytes, by pulling out the few displaced elements, sorting them and merging them back. Plain slices of 32- and 64-bit numbers take this pass with AVX2.

Everything else goes through records: an array of small records, one per element, holding the radix form of the key and the original index. The records are sorted by the core algorithm (a scout pass that picks between reversal, merging a few runs, the displaced-element route and the radix route; the radix route samples the keys, splits at the median, chooses a plan per part and verifies it while counting), then the elements are permuted once. Keys of up to 32 bits become 8-byte records, up to 64 bits 16-byte records, a string a 16-byte pointer-and-length record, anything else a composite record sorted chunk by chunk. A plain slice of numbers or pointers needs no index: the keys themselves are sorted, 4 or 8 bytes per element, and written back (the two zeros of an f32 or f64 share a key and are put back by their rank among the zeros).

Floating point

-0.0 and +0.0 compare equal (and stay in input order); a NaN with the sign bit clear sorts after +inf, one with it set before -inf, ordered by payload. This is a total order, so no input is unsafe; it is not f64::total_cmp, which orders -0.0 before +0.0.

Memory, failure, limits

• Memory. n records of 8, 16 or more bytes (8 for a plain slice of 64-bit numbers, which needs no index), plus the algorithm’s scratch of about n/2 records on full-entropy input, plus count tables of at most 64 KiB (about 400 KiB for a part that is scattered beyond the cache). Elements are permuted through a buffer of n elements, or in place through cycles if that buffer cannot be allocated. Sorted and reversed input, and nearly sorted small elements, need no memory beyond the displaced elements.
• Memory is kept. Freed blocks of 64 KiB and more are kept, up to 32 MiB in total, for the next sort of the process; fresh pages cost more than a sort of a hundred thousand elements. set_memory_cache_limit changes the limit (0 disables it) and release_memory frees the blocks at any time. Without the std feature the cache is behind a spin lock.
• Allocation fails. The sort completes anyway through the standard library’s stable sort with the same order.
• The key function panics. All keys are computed before anything moves, so the slice is unchanged if the panic happens during the first pass over the keys; a panic on a later call (the nearly sorted route compares elements again) leaves every element in the slice, in an unspecified order. A comparator that panics likewise. A comparator that is not a total order gets an unspecified order, or the panic the standard library’s sort documents for it; every element stays in the slice exactly once.
• Limits. At most 2^32 - 1 elements per call and strings shorter than 2^32 bytes; beyond either the call goes to the standard library’s stable sort. The block cache is the only shared state, under its own lock; concurrent sorts are fine.

Features

• std (default): run-time CPU feature detection on x86-64, a mutex for the memory cache, OsStr and Path keys. Without it the crate is no_std + alloc, and the vector paths are used only when enabled at compile time (-C target-feature=+avx2,+bmi2).

Re-exports

pub use key::Desc;

pub use key::Key;

pub use key::desc;

Modules

key

The Key trait and its implementations for the built-in key types.

Macros

bytes_key

Implements Key for a type ordered by a byte string it holds.

fixed_key

Implements Key for a type that maps to a fixed-width unsigned value.

Constants

VERSION

The version of the crate.

Traits

PlainBytes

An element whose every byte is initialised, so that any window of its bytes can be read as an integer or a float: what sort_by_inferred needs. Implemented for the primitive numbers, bool, char and arrays of these; a struct opts in with unsafe impl once it has no padding (#[repr(C)] fields whose sizes add up to the size of the struct, or #[repr(C, packed)]).

Functions

release_memory

Frees the blocks the library keeps for reuse (see the module documentation). Never needed for correctness.

set_memory_cache_limit

Sets how many bytes of freed blocks the library keeps for the next sort (32 MiB by default). 0 disables the cache; the blocks held now stay until release_memory is called.

sort

Sorts the slice by the elements themselves. Stable.

sort_by

Sorts the slice by a comparator. Stable. Sorted, reversed and nearly sorted input is handled on the elements as the key sorts do; input made of long sorted pieces is merged as it is, and everything else is the standard library’s slice::sort_by. Both run on the elements themselves up to 16 bytes and on an array of indices beyond that, so that larger elements move once, at the end.

sort_by_inferred

Sorts the slice by a comparator, guessing the key it compares. Stable, and the same result as sort_by on every input.

sort_by_key

Sorts the slice by a key computed from each element, once per element. Stable.

sort_by_key_ref

Sorts the slice by a key borrowed from each element (a string field, say). Stable.