4 ms·
I checked the Haskell implementation of sort a while ago. Apparently it used to be Quicksort, which has a really elegant recursive implementation in Haskell, bu
by c3534l 7y ago
I checked the Haskell implementation of sort a while ago. Apparently it used to be Quicksort, which has a really elegant recursive implementation in Haskell, but they found that mergesort was actually faster. I wonder if it has anything to do with how a programming language implements lists, or if people just assume QuickSort is the fastest because of threads like these and don't bother trying out alternatives.
- masklinn 7y ago> they found that mergesort was actually faster. I wonder if it has anything to do with how a programming language implements lists It probably also has to do with using a non-in-place quicksort, which is where it really shines. Even more so as you'd implement the low arities using an insertion sort rather than a quicksort, which wouldn't work either for immutable collections.
- deleted 7y ago[deleted]
- switz 7y agoHere are some good answers as to why Haskell switched to mergesort https://stackoverflow.com/a/52238049/240569 https://stackoverflow.com/a/52238049/240569