在几乎排序好的数据上速度更快的修改版归并排序

这是TimSort的实现，Python和Java新版本中默认的排序算法。

完整文档在此。

性能

这仍然是一个极度的工作进行中，性能有很大改进空间。

基准测试是唯一一个在纯稳定Rust中不工作的部分。 benches/bench.rs 是rust-TimSort的，benches/bench_default.rs 是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

许可证

以下任一许可证下授权

• Apache许可证2.0版本， (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)