A modified merge sort that's faster on almost-sorted data

This is an implementation of TimSort, the default sorting algorithm used in Python and newer versions of Java.

Full documentation here.

Build Status

Performance

This is still an extreme work-in-progress, and performance has vast room for improvement.

The benchmarks are the only part that doesn't work in pure stable rust. benches/bench.rs is for rust-TimSort, benches/bench_default.rs is for the default MergeSort that comes with Rust.

``` Running target/release/bench-dae501bb89de0c02

running 16 tests test sortbigrandomlarge ... bench: 3,310,775 ns/iter (+/- 232,896) = 96 MB/s test sortbigrandommedium ... bench: 7,755 ns/iter (+/- 118) = 412 MB/s test sortbigrandomsmall ... bench: 297 ns/iter (+/- 19) = 538 MB/s test sortbigsorted ... bench: 18,038 ns/iter (+/- 251) = 17740 MB/s test sortequals ... bench: 1,342 ns/iter (+/- 93) = 5961 MB/s test sortfewunique ... bench: 66,582 ns/iter (+/- 1,882) = 60 MB/s test sorthuge ... bench: 137,064,148 ns/iter (+/- 2,159,033) = 5 MB/s test sortpartiallysorted ... bench: 1,488,792 ns/iter (+/- 19,015) = 53 MB/s test sortrandomlarge ... bench: 2,010,436 ns/iter (+/- 92,632) = 39 MB/s test sortrandommedium ... bench: 4,134 ns/iter (+/- 39) = 193 MB/s test sortrandomsmall ... bench: 194 ns/iter (+/- 163) = 206 MB/s test sortsorted ... bench: 13,043 ns/iter (+/- 540) = 6133 MB/s test sortstrings ... bench: 11,845,502 ns/iter (+/- 247,501) = 24 MB/s test sorttinyrandomlarge ... bench: 2,049,110 ns/iter (+/- 12,357) = 4 MB/s test sorttinyrandommedium ... bench: 4,227 ns/iter (+/- 98) = 23 MB/s test sorttinyrandomsmall ... bench: 166 ns/iter (+/- 4) = 30 MB/s

test result: ok. 0 passed; 0 failed; 0 ignored; 16 measured

 Running target/release/bench_default-a77273e7b72e7094

running 16 tests test sortbigrandomlarge ... bench: 1,383,147 ns/iter (+/- 31,362) = 231 MB/s test sortbigrandommedium ... bench: 7,107 ns/iter (+/- 162) = 450 MB/s test sortbigrandomsmall ... bench: 288 ns/iter (+/- 8) = 555 MB/s test sortbigsorted ... bench: 464,047 ns/iter (+/- 7,236) = 689 MB/s test sortequals ... bench: 15,959 ns/iter (+/- 949) = 501 MB/s test sortfewunique ... bench: 66,069 ns/iter (+/- 2,187) = 60 MB/s test sorthuge ... bench: 9,503,439 ns/iter (+/- 377,908) = 84 MB/s test sortpartiallysorted ... bench: 501,055 ns/iter (+/- 7,756) = 159 MB/s test sortrandomlarge ... bench: 668,164 ns/iter (+/- 23,727) = 119 MB/s test sortrandommedium ... bench: 3,685 ns/iter (+/- 35) = 217 MB/s test sortrandomsmall ... bench: 187 ns/iter (+/- 15) = 213 MB/s test sortsorted ... bench: 266,431 ns/iter (+/- 7,553) = 300 MB/s test sortstrings ... bench: 2,299,735 ns/iter (+/- 58,825) = 127 MB/s test sorttinyrandomlarge ... bench: 737,314 ns/iter (+/- 18,718) = 13 MB/s test sorttinyrandommedium ... bench: 4,141 ns/iter (+/- 45) = 24 MB/s test sorttinyrandomsmall ... bench: 160 ns/iter (+/- 11) = 31 MB/s

test result: ok. 0 passed; 0 failed; 0 ignored; 16 measured ```

License

Licensed under either of these: