# 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.