4 ms·
Summary: this is a non-recursive merge sort with improvements. Benchmark of quadsort() versus C qsort(): * ~10x faster on forward-order items * ~2x faster on
by jph 7y ago
Summary: this is a non-recursive merge sort with improvements.
Benchmark of quadsort() versus C qsort():
* ~10x faster on forward-order items
* ~2x faster on reverse-order items
* ~equivalent on random-order items
Improvements:
* Ordering: when blocks of items are in order, or in reverse-order, then do special case handling, which gives quadsort O(n + log n) instead of qsort O(n * log n).
* Boundaries: compare data rather than traditional merge sort wasteful boundary checks.
- eru 7y agoIf you have a k sorted (or reverse sorted) blocks, you can get O(n log k) performance in merge sort variants. Especially, if k is a small fixed constant, like 1 or 2 or 10, you should get linear performance. A few language's standard library sorts implement that already. For a serious implementation, of course, you not only care about the asymptotic performance, but also absolute runtimes.
- chalst 7y agoGood summary. Quibble: O(n + log n) = O(n).
- kannmig 7y agoI think OP made the distinction intentional to “show their working”, so to speak.