This is a PowerSort implementation in Rust.
PowerSort is a run-adaptive mergesort, relating the problem of finding a good merge order to the problem of building optimal binary search trees. Specifically, it adapts an heuristic that build nearly optimal binary search trees. PowerSort is similar to TimSort: proceeding from left to right over the input detecting already existing runs and deciding if a merge is useful.
TimSort uses a quite complex set of rules to decide when to merge, the rules themselves where empirically derived and require looking at the top three elements of the run stack to maintain the invariants. PowerSort on the other hands only requires the calculationg of a single integer between runs which decides when it is beneficial to merge. This integer is called the power of the run and related to the depth the node would have in the resulting merge tree following the bisection heuristic.
src/powersort.rs contains the main implementation from scratch. src/powersort_final.rs contains the implementation with the most performant alternatives of merging, extend run, and running from right to left, it performs faster than powersort.rs, but still not as fast as Rust's default implementation. The modified Rust codebase version is found in src/sort.rs.
src/alternatives.rs contain alternatives for the dependant algorithms, src/powersort_alternatives.rs for the PowerSort implementation.
The data used in the benchmarking is generated by src/sequences.rs.
Finally, benches contain the benchmarking code and it is not particularly beautiful as its contains quite a bit of repeated code for the purpose of benchmarking.