Sorting algorithms implemented in Rust.
toml
[dependencies]
sorting_rs = "1.2.0"
rust
use sorting_rs::*;
&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.| 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 + m
2 | nm
| |
| Bitonic | method based on building a sorting network | nlog
2
n
| nlog
2
n
| nlog
2
n
|
| Bubble | bad for sorted or reversed input | n
2
; n
2
| n
; 1
| 1
|
| Cocktail | little performance improvement over bubble sort | n
2
| n
| 1
|
| Comb | speeds up when data is nearly sorted | n
2
| nlogn
| 1
|
| Cycle | uses minimum amount of writes, good for memory with limited TBW | n
2
| n
2
| 1
|
| Gnome | simple and slow, works with one item at a time | n
2
| 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 | n
2
; n
2
| n
; 1
| 1
|
| Merge | independent of data distribution | nlogn
| nlogn
| n
|
| Odd-even | presented to be effective on processors with local interconnections | n
2
| n
| 1
|
| Odd-even Batcher | more efficient version of odd-even sort | log
2
n
| log
2
n
| logn
2
|
| Pancake | swaps data a lot and not so effective in practice | n
3
; 2n - 3
| n
2
| n
|
| Quick | bad for sorted or reversed input | n
2
| nlogn
| logn
|
| Quick dual | enchanced version of quicksort | n
2
| 2nlnn
| logn
|
| Ksort | quicksort variant, faster than heap at less than 7 million elements | n
2
| nlog
2n
| logn
|
| Selection | the least number of swaps among all the algorithms | n
2
; n
| n
2
; 1
| 1
|
| Double selection | modified selection sort with more workload, but better efficiency | n
2
; n
| n
2
; 1
| higher than Selection |
| Shellsort | it is optimization of insertion sort | n
3/2
or nlogn
2
| 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 | n
2.7095
| | n
|
New algorithms implementations are planned in future