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 40% 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 was designed by Orson Peters and first published at: https://github.com/orlp/pdqsort

Quoting it's designer: "Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns. pdqsort is an extension and improvement of David Musser's introsort."

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.