3 ms·
Quicksort is actually O(n^2) in degenerate cases but as you note its expected to operate in-place. Proper in-place algos written in Haskell read like the impera
by lolc 10y ago
Quicksort is actually O(n^2) in degenerate cases but as you note its expected to operate in-place. Proper in-place algos written in Haskell read like the imperative versions. This sort code made it into FP lore as a quicksort equivalent which it isn't. It's just neat.
In this case it is not clear the author intended to claim their code has quicksort properties. The "why don't they" question at the bottom could be read as "Or is it quick-sort?" Hey I'm being generous because reading just the slides is bound to miss subtext.
- jacobparker 10y agoYeah, I wasn't being very generous. However, naming the function "qsort" is pretty dishonest. I agree that the proper quick-sort implementation is going to look pretty imperative (and involve mutation) which is why I get a bit annoyed at fake-quick-sort being used to demo how pretty FP makes your code... (I agree that this implementation is neat. I think it's a great way to explain sorting.) (naive qsort is O(n^2) in the worst case (with pivot selection it is Theta(nlogn), though,) but the functional-linked-list-sort is O(n^2) in all cases... :))