3 ms·

I wrote a pretty concise version of it a while ago to convince myself it was possible [1]. It isn't as short as the naive (incorrect) quicksort using lists, but

I wrote a pretty concise version of it a while ago to convince myself it was possible [1]. It isn't as short as the naive (incorrect) quicksort using lists, but every line has a very clear purpose. Most implementations on Rosetta code in other languages [2] seem to be about as long. [1] https://gist.github.com/harpocrates/bbed7b6837d524aafa02 https://gist.github.com/harpocrates/bbed7b6837d524aafa02 [2] https://rosettacode.org/wiki/Sorting_algorithms/Quicksort https://rosettacode.org/wiki/Sorting_algorithms/Quicksort

Athas 10y ago
Thank you, that is a very nice implementation! I think the key is that the vector library is very well designed - it has certainly been the cause of the majority of my Haskell performance successes. I'll say that your implementation benefits from being able to access partitioning as a library function - the actual implementation of unstablePartition is not particularly pretty (but it is conceptually simple).