Skip to content
This repository has been archived by the owner on Aug 27, 2020. It is now read-only.
/ rust-timsort Public archive

Rust implementation of the modified MergeSort used in Python and Java

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

notriddle/rust-timsort

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

28 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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 sort_big_random_large   ... bench:   3,310,775 ns/iter (+/- 232,896) = 96
MB/s
test sort_big_random_medium  ... bench:       7,755 ns/iter (+/- 118) = 412 MB/s
test sort_big_random_small   ... bench:         297 ns/iter (+/- 19) = 538 MB/s
test sort_big_sorted         ... bench:      18,038 ns/iter (+/- 251) = 17740
MB/s
test sort_equals             ... bench:       1,342 ns/iter (+/- 93) = 5961 MB/s
test sort_few_unique         ... bench:      66,582 ns/iter (+/- 1,882) = 60
MB/s
test sort_huge               ... bench: 137,064,148 ns/iter (+/- 2,159,033) = 5
MB/s
test sort_partially_sorted   ... bench:   1,488,792 ns/iter (+/- 19,015) = 53
MB/s
test sort_random_large       ... bench:   2,010,436 ns/iter (+/- 92,632) = 39
MB/s
test sort_random_medium      ... bench:       4,134 ns/iter (+/- 39) = 193 MB/s
test sort_random_small       ... bench:         194 ns/iter (+/- 163) = 206 MB/s
test sort_sorted             ... bench:      13,043 ns/iter (+/- 540) = 6133
MB/s
test sort_strings            ... bench:  11,845,502 ns/iter (+/- 247,501) = 24
MB/s
test sort_tiny_random_large  ... bench:   2,049,110 ns/iter (+/- 12,357) = 4
MB/s
test sort_tiny_random_medium ... bench:       4,227 ns/iter (+/- 98) = 23 MB/s
test sort_tiny_random_small  ... 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 sort_big_random_large   ... bench:   1,383,147 ns/iter (+/- 31,362) = 231
MB/s
test sort_big_random_medium  ... bench:       7,107 ns/iter (+/- 162) = 450 MB/s
test sort_big_random_small   ... bench:         288 ns/iter (+/- 8) = 555 MB/s
test sort_big_sorted         ... bench:     464,047 ns/iter (+/- 7,236) = 689
MB/s
test sort_equals             ... bench:      15,959 ns/iter (+/- 949) = 501 MB/s
test sort_few_unique         ... bench:      66,069 ns/iter (+/- 2,187) = 60
MB/s
test sort_huge               ... bench:   9,503,439 ns/iter (+/- 377,908) = 84
MB/s
test sort_partially_sorted   ... bench:     501,055 ns/iter (+/- 7,756) = 159
MB/s
test sort_random_large       ... bench:     668,164 ns/iter (+/- 23,727) = 119
MB/s
test sort_random_medium      ... bench:       3,685 ns/iter (+/- 35) = 217 MB/s
test sort_random_small       ... bench:         187 ns/iter (+/- 15) = 213 MB/s
test sort_sorted             ... bench:     266,431 ns/iter (+/- 7,553) = 300
MB/s
test sort_strings            ... bench:   2,299,735 ns/iter (+/- 58,825) = 127
MB/s
test sort_tiny_random_large  ... bench:     737,314 ns/iter (+/- 18,718) = 13
MB/s
test sort_tiny_random_medium ... bench:       4,141 ns/iter (+/- 45) = 24 MB/s
test sort_tiny_random_small  ... 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:

About

Rust implementation of the modified MergeSort used in Python and Java

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages