sortrs

A fast unstable sort for Rust using introspective sort.

The default Rust sort is provided std::slice::SliceExt::sort_by. It is implemented using a merge sort, which performs an in-place stable sort with O(n log n) complexity and allocates approximately 2 * n T bytes. The comparison requries the Ord trait.

If a stable sort is not required, then a different sort algorithm may be used which doesn't perform memory allocation and only requires the PartialOrd trait.

Introsort or introspective sort is the default unstable sort algorithm used by most implementations of C++ std::sort.

From Wikipedia on Introsort:

The sort is implemented using the Introsort algorithm. Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. This combines the good parts of both algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort.

Performance

Introsort outperforms Rust's default merge sort in most of it's own benchmarks, it particularly excels with sorted or nearly sorted data.

The data below was generated by cargo bench on an Intel(R) Core(TM) i7-4710HQ CPU @ 2.50GHz running Linux 3.16.0-28 x86_64.

introsort_big_random_large   ... bench:   780015 ns/iter (+/- 14249) = 410 MB/s
introsort_big_random_medium  ... bench:     4304 ns/iter (+/- 88) = 743 MB/s
introsort_big_random_small   ... bench:      138 ns/iter (+/- 4) = 1159 MB/s
introsort_big_sorted         ... bench:   169422 ns/iter (+/- 4132) = 1888 MB/s
introsort_random_large       ... bench:   531086 ns/iter (+/- 13947) = 150 MB/s
introsort_random_medium      ... bench:     2939 ns/iter (+/- 160) = 272 MB/s
introsort_random_small       ... bench:       99 ns/iter (+/- 1) = 404 MB/s
introsort_sorted             ... bench:    95669 ns/iter (+/- 3765) = 836 MB/s
stdsort_big_random_large     ... bench:   972799 ns/iter (+/- 31151) = 328 MB/s
stdsort_big_random_medium    ... bench:     4257 ns/iter (+/- 195) = 751 MB/s
stdsort_big_random_small     ... bench:      134 ns/iter (+/- 6) = 1194 MB/s
stdsort_big_sorted           ... bench:   396306 ns/iter (+/- 9500) = 807 MB/s
stdsort_random_large         ... bench:   564020 ns/iter (+/- 13495) = 141 MB/s
stdsort_random_medium        ... bench:     2969 ns/iter (+/- 145) = 269 MB/s
stdsort_random_small         ... bench:      102 ns/iter (+/- 6) = 392 MB/s
stdsort_sorted               ... bench:   242503 ns/iter (+/- 5684) = 329 MB/s

Usage

Add this in your Cargo.toml:

[dependencies]
sortrs = "*"

And this in your crate root:

extern crate sortrs;