fix: new sorting algorithm#1904
Conversation
Benchmark sources:AssemblyScript & JavaScript: Rust wasm: Results: Chrome 91AS sort 100_000 doubles : 18.70 ms AS NEW sort 100_000 doubles : 11.30 ms Rust (wasm) sort 100_000 doubles : 19.80 ms JS sort 100_000 doubles : 43.20 ms Firefox 89AS sort 100_000 doubles : 22.00 ms AS NEW sort 100_000 doubles : 12.00 ms Rust (wasm) sort 100_000 doubles : 23.00 ms JS sort 100_000 doubles : 33.00 ms Safari 14.2 TPAS sort 100_000 doubles : 21.00 ms AS NEW sort 100_000 doubles : 16.00 ms Rust (wasm) sort 100_000 doubles : 27.00 ms JS sort 100_000 doubles : 23.00 ms |
|
Yayy! |
dcodeIO
left a comment
There was a problem hiding this comment.
Can't really comment on the algorithm yet, but have a few more general comments :)
Co-authored-by: Daniel Wirtz <dcode@dcode.io>
New sorting algorithm based on "Power Sort" from "Nearly-Optimal Mergesorts" (May 2018) paper (https://arxiv.org/pdf/1805.04154.pdf). Also this implementation contains highly optimized novel insertion sort as part of main algorithm.
The previous algorithm was unstable which forced us to do fallback on the slow insertion sort for reference types for following ECMAScript spec. Which, of course, was very undesirable.
Features:
Stable
Faster than TimSort (approx 1.5-2x)
Faster than JS sort (TimSort) (approx 5x)
Has a mathematical proof of correctness, unlike TimSort (See paper)
I've read the contributing guidelines