Pattern-defeating quicksort
This sort is significantly faster than slice::sort in Rust. In particular, it sorts
random arrays of integers approximately 45% faster. The key drawback is that it is an unstable
sort (i.e. may reorder equal elements). However, in most cases stability doesn't matter anyway.
The algorithm is based on pdqsort by Orson Peters, published at: https://github.com/orlp/pdqsort
Now in stable Rust
If you're using Rust 1.20 or newer, you don't need this crate. The sort is now implemented in libcore.
Use it like this:
let mut v = [-5, 4, 1, -3, 2];
v.sort_unstable();
assert!(v == [-5, -3, 1, 2, 4]);See documentation for more information.
Properties
- Best-case running time is
O(n). - Worst-case running time is
O(n log n). - Unstable, i.e. may reorder equal elements.
- Does not allocate additional memory.
- Uses
#![no_std].
Examples
extern crate pdqsort;
let mut v = [-5i32, 4, 1, -3, 2];
pdqsort::sort(&mut v);
assert!(v == [-5, -3, 1, 2, 4]);
pdqsort::sort_by(&mut v, |a, b| b.cmp(a));
assert!(v == [4, 2, 1, -3, -5]);
pdqsort::sort_by_key(&mut v, |k| k.abs());
assert!(v == [1, 2, -3, 4, -5]);A simple benchmark
Sorting 10 million random numbers of type u64:
| Sort | Time |
|---|---|
| pdqsort | 370 ms |
| slice::sort | 668 ms |
| quickersort | 777 ms |
| rdxsort | 602 ms |