[klibertp]

If I didn't know how quicksort works - and I had to learn, since for some reason in FP languages quicksort is typically next after "hello world" - I would struggle to make sense of the pictures, I think. However, it's absolutely brilliant as a memory refresher: it packs so much info in so little space that it's insanely efficient. I imagine it would pair well with a good textbook on algorithms.

[TeMPOraL]

> for some reason in FP languages quicksort is typically next after "hello world"

Because the recursive implementation is surprisingly straightforward and concise, and more-less demonstrates what the whole paradigm is about. As much as I hate to admit it, it's a good learning artifact.

[hinkley]

It’s straightforward to a programmer. Who doesn’t need an ikea diagram in the first place.

This is why developer docs are trash. Because 90% of us can’t even identify when we are talking over everyone’s heads.

[zahlman]

Am I alone in that I always felt like mergesort was easier to explain (and the O(n lg n) behaviour was easier to prove)?

[Dwedit]

Merge Sort is much easier to explain when you do the non-recursive version that's upside-down. Merge size 1 together, merge size 2 together, merge size 4 together, merge size 8 together, etc...

[enedil]

O(n lg n) is indeed hard to prove for quicksort, because it is not even true in the general case. Worst case is O(n^2).

[flexagoon]

> Because the recursive implementation is surprisingly straightforward and concise

It's also technically not quicksort

[jason_s]

> since for some reason in FP languages quicksort is typically next after "hello world"

How does FP handle the random selection?

[klibertp]

They use the first element. Like, it's random enough, right? :) (I mean, it still works, but goes badly for lists already sorted in reverse, etc.)

[shpongled]

There's no problem with randomness in FP?

You could use a monad/external state for an OS-level RNG, or define a purely functional PRNG

[shawn_w]

It's usually quicksorting a linked list, where a random pivot, median of three, etc. are terrible for performance.

(Merge sort is of course the natural sort for lists, but qs is like 2 lines of Haskell so it gets demoed for being clever)

[tmtvl]

Just do the Sedgewick thing and take the median of the first, middle, and last elements.

[Arch-TK]

Quicksort in FP?

Surely you mean mergesort, that's the classic FP sorting example.

[riffraff]

quicksort, e.g. the haskell[0] example is quite well known. Problem is, it's not real since it doesn't work in place defeating the whole point.

[0] https://qnikst.github.io/posts/2020-10-18-quicksort.html

[notpushkin]

It really shines if you want a shortcut on a whiteboard interview, though.

[hinkley]

Step six: draw the rest of the fucking owl.

Yeah this is lousy. This wouldn’t teach anyone anything.