#sort #sorting #no_std

no-std count_sort

O(n) sorting library for large datasets with small range of possible values

9 releases

✓ Uses Rust 2018 edition

0.1.8 Jul 11, 2019
0.1.7 Jul 10, 2019
0.1.3 Apr 13, 2019

#168 in Algorithms

Download history 41/week @ 2019-04-11 4/week @ 2019-04-18 11/week @ 2019-04-25 1/week @ 2019-05-02 7/week @ 2019-05-09 10/week @ 2019-05-16 4/week @ 2019-05-30 18/week @ 2019-06-06 12/week @ 2019-06-20 21/week @ 2019-06-27 51/week @ 2019-07-04

63 downloads per month

MIT license

4KB

Count Sort

A fast sorting library implementing count sort algorithm which is O(n + k). Designed for very quickly sorting large amounts of data with small range of possible values. It now supports no_std

Currently only supports u8.

Goals

Add support for more types including i8, u16 and i16

Performance

Time to clone and sort randomly generated Vec of length specified below. Demonstrates for which lengths it is faster, and for which lengths the overhead is too much.

length sort_u8 .sort() .sort_unstable() dmsort
0 9.3944 ns 11.633 ns 11.887 ns 11.427 ns
1 24.074 ns 25.148 ns 25.700 ns 25.442 ns
4 215.06 ns 48.536 ns 49.364 ns 110.13 ns
16 370.30 ns 223.30 ns 238.12 ns 429.16 ns
64 935.84 ns 2.1638 us 1.4000 us 1.8457 us
256 2.0890 us 11.445 us 6.5242 us 7.3119 us
1024 3.8468 us 56.754 us 27.414 us 30.193 us
4096 7.3327 us 255.55 us 77.200 us 85.214 us
16384 19.219 us 1.0981 ms 233.50 us 265.55 us
65536 73.449 us 4.6771 ms 794.74 us 914.10 us
262144 296.26 us 19.938 ms 3.1294 ms 3.4867 ms

Usage

Add dependency to Cargo.toml

[dependencies]
count_sort = "0.1"

And add the following to your code:

extern crate count_sort;

fn main () {
	let mut data: Vec<u8> = vec![252, 107, 81, 35, 185, 18, 175, 130, 37, 166];
	count_sort::sort_u8(&mut data);
	println!("{:?}", data);

}

No runtime deps