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:


  • 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].


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]);



Sorts a slice.


Sorts a slice using compare to compare elements.


Sorts a slice using f to extract a key to compare elements by.