crumsort-rs

A parallelized Rust port of crumsort.

The goal of this port is to excel at sorting well-distributed data which is why it is not an exact 1:1 replica.

Temporary caveats

There are a few limitations given some of the constraints when this was originally written:

• sorts uniform data faster than crumsort, but severly skewed distributions slower (missing crumsort_analyze function)
• intended as a solution for sorting large (u64 or u128) integers
• only sorts Copy + Default data as a way to limit the use of unsafe
• missing un-parallelized version (data needs to implement Send)
• missing *_by and *_by_key sorting alternatives (data needs to implement Ord)

Please feel free to submit improvements in any of these area by submitting a pull request.

Benchmarks against parallel pdqsort (Rayon)

All banchmarks run with the bench example on an M1 Pro:

cargo run --release --example bench

Uniformly distributed random u32s

Uniformly distributed random u64s

Note

This is not an officially supported Google product.