7 releases (4 stable)

Uses old Rust 2015

1.0.3 Mar 27, 2017
1.0.2 Mar 24, 2017
0.1.2 Feb 11, 2017
0.1.1 Feb 3, 2017
0.1.0 Jan 26, 2017

#587 in Algorithms

Download history 204/week @ 2022-06-03 184/week @ 2022-06-10 126/week @ 2022-06-17 218/week @ 2022-06-24 169/week @ 2022-07-01 157/week @ 2022-07-08 143/week @ 2022-07-15 204/week @ 2022-07-22 206/week @ 2022-07-29 210/week @ 2022-08-05 125/week @ 2022-08-12 111/week @ 2022-08-19 210/week @ 2022-08-26 400/week @ 2022-09-02 289/week @ 2022-09-09 158/week @ 2022-09-16

1,084 downloads per month

Apache-2.0/MIT

33KB
517 lines

Pattern-defeating quicksort

Build Status License Cargo Documentation

This sort is 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 pdqsort by Orson Peters, published at: https://github.com/orlp/pdqsort

Now in nightly Rust

If you're using nightly Rust, you don't need this crate. The sort is as of recently implemented in libcore.

Use it like this:

#![feature(sort_unstable)]

let mut v = [-5, 4, 1, -3, 2];

v.sort_unstable();
assert!(v == [-5, -3, 1, 2, 4]);

See The Unstable Book for more information.

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

A simple benchmark

Sorting 10 million random numbers of type u64:

Sort Time
pdqsort 370 ms
slice::sort 668 ms
quickersort 777 ms
rdxsort 602 ms

No runtime deps