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 `compare` to compare elements.
sort_by_key	Sorts a slice using `f` to extract a key to compare elements by.