3 ms·
> "just run a final pass of insertion sort to make it useful!" (And if this insertion sort won't complete in O(n), say <= 3n, then, fallback to Quicksort, so w
by KajMagnus 6y ago
> "just run a final pass of insertion sort to make it useful!"
(And if this insertion sort won't complete in O(n), say <= 3n, then, fallback to Quicksort, so won't turn into O(n^2) just because the ML alg hit a corner case)
- mkl 6y agoPossibly better would be Timsort (used in Python, Java, V8, etc.), as it's "designed to take advantage of runs of consecutive ordered elements that already exist": https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort
- eru 6y agoHaskell's standard library sort, a variant of merge sort, also makes use of runs. It runs in O(n log (number of runs)). It's quite a lot simpler than Timsort.