Crate pdqsort [−] [src]
Pattern-defeating quicksort.
This sort is significantly faster than the standard 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
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]);
Functions
sort |
Sorts a slice. |
sort_by |
Sorts a slice using |
sort_by_key |
Sorts a slice using |