Haskell quicksort - what is it really?

Question

As they say, "true quicksort sorts in-place" . So, the standard Haskell shortcode for quicksort ,

quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter (< p) xs greater = filter (>= p) xs 

what algorithm / computational process does he describe in the end?

This, of course, is not what Tony Hoar , devoid of his most defining function, developed the local partitioning algorithm.

(the answer may be well known, but not yet included in SO).

---

correction: this question is actually a duplicate: answer known on SO after all: cf. The temporal complexity of a pseudo-expression .

Answer 1

These are quicksort for linked listings.

Yes, it's fast, just out of place. It corresponds to a high-level algorithm for quick sorting when changing a low-level implementation in accordance with the data structure of linked lists. This is why it quickly sorts related lists.

I would rather say that "quicksort was originally designed to work on site" than "real quicksort." There are many options for quick sorting, including choosing random points to avoid worse behavior, etc. This is a reasonable, clear definition of quicksort for linked lists.

This definition exactly matches how we teach quicksort to 16-year-old math students in the UK. (We study algorithms, not programming.) It really hides the purpose and design, so we don’t teach this detail, even though it is a million miles from learning functional programming or related lists. (This does not change the fact that a packet-switched local exchange algorithm is best when you have arrays of disruptive updates.)

There is a time penalty for this definition, as it iterates over the list twice for two subscriptions. Of course, you can rewrite this to a section, not a filter, but I argue that this is an optimization, not a change to the fundamental algorithm here, quicksort.

Answer 2

All algorithms in place require some “ceremony” in Haskell, where the volatile state is hidden behind the monad. Algorithm above fast, just out of place.

Answer 3

The supposed answer (from here ) is that it is a "really deforested tree species." Turns out this is also mentioned on haskellwiki .