Crate pdqsort [−] [src]

Pattern-defeating quicksort

This sort is in most cases 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 pattern-defeating quicksort 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.