Crate pdqsort

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.