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.

Introsort outperforms Rust's default merge sort in all 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:    735398 ns/iter (+/- 8984) = 434 MB/s
introsort_big_random_medium  ... bench:      4165 ns/iter (+/- 317) = 768 MB/s
introsort_big_random_small   ... bench:       136 ns/iter (+/- 3) = 1176 MB/s
introsort_big_sorted         ... bench:    147710 ns/iter (+/- 5675) = 2166 MB/s
introsort_random_large       ... bench:    498945 ns/iter (+/- 7336) = 160 MB/s
introsort_random_medium      ... bench:      2764 ns/iter (+/- 133) = 289 MB/s
introsort_random_small       ... bench:        96 ns/iter (+/- 2) = 416 MB/s
introsort_sorted             ... bench:     87369 ns/iter (+/- 1538) = 915 MB/s
stdsort_big_random_large     ... bench:    932398 ns/iter (+/- 18704) = 343 MB/s
stdsort_big_random_medium    ... bench:      4218 ns/iter (+/- 82) = 758 MB/s
stdsort_big_random_small     ... bench:       142 ns/iter (+/- 4) = 1126 MB/s
stdsort_big_sorted           ... bench:    375462 ns/iter (+/- 7778) = 852 MB/s
stdsort_random_large         ... bench:    550943 ns/iter (+/- 7290) = 145 MB/s
stdsort_random_medium        ... bench:      2822 ns/iter (+/- 76) = 283 MB/s
stdsort_random_small         ... bench:        96 ns/iter (+/- 2) = 416 MB/s
stdsort_sorted               ... bench:    236815 ns/iter (+/- 8846) = 337 MB/s

Add this in your Cargo.toml:

[dependencies]
sortrs = "*"

And this in your crate root:

extern crate sortrs;