Uses old Rust 2015
3.0.1 


3.0.0 

2.2.0 

2.1.1 

1.0.0 

#58 in #sorting
725 downloads per month
Used in 9 crates
(4 directly)
37KB
509 lines
Deprecated
There's really no point in using this library any more. Everything good about it has been incorporated into std::sort_unstable in the Rust standard library, which even uses a better algorithm. Just use that.
quickersort
This is an implementation of the introsort sorting algorithm.
This is a fork of veddan/rustintrosort, with a number of improvements.
To use with cargo, add the following to your Cargo.toml
:
[dependencies]
quickersort = "3.0"
and in your crate root, add
extern crate quickersort;
Interface
The interface is similar to the standard library sort
and sort_by
functions.
An example:
extern crate quickersort;
fn main() {
let mut ss = vec!["Introsort", "or", "introspective", "sort", "is",
"a", "hybrid", "sorting", "algorithm", "that",
"provides", "both", "fast", "average",
"performance", "and", "(asymptotically)", "optimal",
"worstcase", "performance"];
quickersort::sort(&mut ss[..]);
println!("alphabetically");
for s in ss.iter() { println!("\t{}", s); }
quickersort::sort_by(&mut ss[..], &a, b a.len().cmp(&b.len()));
println!("\nby length");
for s in ss.iter() { println!("\t{}", s); }
}
Unlike the standard library sort function, introsort is not a stable sort.
Details
At its heart, it is a dualpivot quicksort. For partition with many equal elements, it will instead use a singlepivot quicksort optimized for this case. It detects excessive recursion during quicksort and switches to heapsort if need be, guaranteeing O(n log(n)) runtime on all inputs. For small partitions it uses insertion sort instead of quicksort.
Unlike the std
sort, it does not allocate.
Performance
It is quite fast, outperforming the standard sort on all data sets I have tried. The performance difference varies depending on the characteristics of the data. On large, completely random arrays, introsort is only 510% faster than the standard sort. However, introsort's performance is greatly improved if the data has few unique values or is (partially) sorted (including reversed data). For sorted data, introsort is ~45 times faster, and for data with few unique values it can be more than 20 times faster.
Detailed benchmark data (only for integers as of now) is available.
Floating point
The crate, if built with the "float" feature (which is the default), also includes a sort_floats
function.
Floating point numbers are not Ord
, only PartialOrd
, so sort
can not be used on them.
The ordering used by sort_floats
is
 inf  < 0  0  +0  > 0  +inf  NaN 
sort_floats
is much more efficient than passing a comparator function implementing this ordering to sort_by
.