flakusha/sorting_rs

Sorting algorithms implemented in Rust

sorting_rs

Sorting algorithms implemented in Rust.

Usage

1. Add this dependency and please consider it's version into your Cargo.toml:

[dependencies]
sorting_rs = "1.2.0"

2. Use available sorting algorithms in your Rust code:

use sorting_rs::*;

3. API for every sorting function is pretty the same: you just have to pass mutable reference: &mut [T], or vec![T, T, T, ...]. T should have PartialOrd trait, sometimes you may need Copy or Clone traits, though all implementations try to avoid this kind of additional requirements.
4. For more information about origin of algorithms and implementation details, please read modules documentation. Wikipedia is nice starting point too.

This library contains following sorting algorithms:

Sorting algorithm	Features and downsides	Worst-case performance O(): comparisons; swaps	Best-case performance O(): comparisons; swaps	Space complexity O()
Bingo	aims to be faster than selection sort if there are duplicates	n + m2	nm
Bitonic	method based on building a sorting network	nlog2n	nlog2n	nlog2n
Bubble	bad for sorted or reversed input	n2; n2	n; 1	1
Cocktail	little performance improvement over bubble sort	n2	n	1
Comb	speeds up when data is nearly sorted	n2	nlogn	1
Cycle	uses minimum amount of writes, good for memory with limited TBW	n2	n2	1
Gnome	simple and slow, works with one item at a time	n2	n	1
Heap	independent of data distribution	nlogn	nlogn	1
Weak Heap	independent of data distribution, decreased number of comparisons	nlogn	nlogn	1
N-Heap	should be faster than default heap. N = 3	nlogn	nlogn	1
Bottom-up Heap	upgraded version of heapsort with decreased number of comparisons	nlogn	nlogn	1
Insertion	simple, but less effective than quicksort, heapsort or merge sort	n2; n2	n; 1	1
Merge	independent of data distribution	nlogn	nlogn	n
Merge Bottom-up	independent of data distribution, modified version of mergesort	nlogn	nlogn	n
Odd-even	presented to be effective on processors with local interconnections	n2	n	1
Odd-even Batcher	more efficient version of odd-even sort	log2n	log2n	logn2
Pancake	swaps data a lot and not so effective in practice	n3; 2n - 3	n2	n
Quick	bad for sorted or reversed input	n2	nlogn	logn
Quick dual	enchanced version of quicksort	n2	2nlnn	logn
Ksort	quicksort variant, faster than heap at less than 7 million elements	n2	nlog2n	logn
Selection	the least number of swaps among all the algorithms	n2; n	n2; 1	1
Double selection	modified selection sort with more workload, but better efficiency	n2; n	n2; 1	higher than Selection
Shellsort	it is optimization of insertion sort	n3/2 or nlogn2	nlogn	1
Slow	it's slow, who would ever need it?
Smooth	variant of heapsort, good for nearly sorted data	nlogn	n	1
Stooge	it's a bit faster than slow sort	n2.7095		n

New algorithms implementations are planned in future