[HN Gopher] Quicksort explained IKEA-style
___________________________________________________________________
Quicksort explained IKEA-style
Author : foehrenwald
Score : 270 points
Date : 2025-09-21 11:35 UTC (3 days ago)
(HTM) web link (idea-instructions.com)
(TXT) w3m dump (idea-instructions.com)
| a022311 wrote:
| This is so cool! Not only is the design similar, but just like
| the real IKEA instructions, I can't understand them! This is as
| realistic as it gets.
| musicale wrote:
| Missing the instruction panel where the customer is attempting
| to follow the baffling instructions and has to use a wired
| phone to call the store for help.
|
| Getting quicksort's boundary conditions right (avoiding off-by-
| one errors, infinite recursion, etc.) can be tricky.
|
| Another popular algorithm that can be hard to get right is
| binary search.
| JdeBP wrote:
| BINARY SEARCH has you covered. (-:
|
| * https://idea-instructions.com/binary-search/
| jalk wrote:
| Stuck in second round of step 2, since there is no middle
| cup to lift!
| NooneAtAll3 wrote:
| at best I can see trouble in interpreting "throw cube and shade
| a bar" as "choose randomly"
|
| but if you don't understand it at all... I have bad news for
| you
| xnx wrote:
| Would be better if the die had lettered sides that matched up
| to the bar positions. With "3" it's hard to be certain it's
| the bar position and not the height.
| jrmg wrote:
| I can understand it after some deciphering, but I think
| that's only because I already know quicksort. I'd be
| interested in seeing if anyone new to sorting algorithms
| finds it illuminating.
|
| Then again, maybe that's not important to the author - it
| _is_ a pretty funny illustration to those in the know.
| tlahtinen wrote:
| I'm a programmer (after a fashion) but I don't know how
| quicksort works.
|
| This is how I understand it after reading these
| instructions, without looking up any further explanation:
|
| 1. Choose a random element as the 'center' point of the
| sort
|
| 2. That element defines the maximum 'height' (value)
|
| 3. Anything that is larger than that value, is moved to the
| right side of the 'center'
|
| 4. Anything that is smaller than that value, is moved to
| the left side of the center. After this, the array is
| partially sorted.
|
| 5. The sorting process is repeated on both 'sides'
| independently, picking a new random center element and so
| on
|
| What isn't clear, is how often the process needs to be
| repeated, or when the algorithm 'knows' that the sorting
| has been finished - surely it can't be just three
| iterations?
|
| By now I've already looked up how the algorithm actually
| works, but the above is what I got out of the illustration
| :)
| klibertp wrote:
| Yeah, that's about it. Personally, I'm not sure I'd get
| this much out of the picture, but you can see the
| information is there.
|
| > surely it can't be just three iterations?
|
| To save others a search: you stop when the remaining sub-
| arrays are sorted by definition (ie. [] or [x]/size of 0
| or 1).
| tialaramex wrote:
| Also, to save any further puzzling: In practice the very
| fast sort you use, even if it is labelled "Quicksort"
| probably doesn't actually do this "all the way down" even
| though that's the strict algorithm.
|
| They'll have a highly optimised small sort and use that
| whenever sorting very small things. So e.g. IPN Sort the
| Rust stdlib unstable sort will do this for 16 items, even
| though for a big slice it'd quick sort them by default,
| once it's down to say 10 items they're going to the
| specialised small sort.
|
| Any serious "fast" sort in 2025 will be a hybrid, using
| several of these classic sorting algortihms, plus other
| insights to produce the overall best solution to their
| problem on modern hardware.
| klibertp wrote:
| 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.
| jason_s wrote:
| > since for some reason in FP languages quicksort is
| typically next after "hello world"
|
| How does FP handle the random selection?
| klibertp wrote:
| 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 wrote:
| 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
| Arch-TK wrote:
| Quicksort in FP?
|
| Surely you mean mergesort, that's the classic FP sorting
| example.
| riffraff wrote:
| 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
| TeMPOraL wrote:
| > _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.
| HarHarVeryFunny wrote:
| Seems to be:
|
| 1) Pick a random (dice roll) pivot
|
| 5) Move all values less than pivot before it, all greater than
| after it
|
| 6) Recurse to sort elements before & after pivot
| thomasmg wrote:
| I agree, IKEA instructions are great. A bit related are
| railroad diagrams, like the one of the JSON syntax [2].
|
| I worked on Rubik's cube solving instructions for beginners [1]
| (for my children initially), but then I found it would be so
| much better if the instructions are IKEA style. (Then I vibe-
| coded a Rubik's cube 2D and 3D model, and now I stopped working
| on this. Something for later.) For the cube, I want to
| implement the algorithm, and then from the program create IKEA
| instruction (or a mix of IKEA and railroad diagram). That way I
| can be sure I didn't skip any steps in the instructions.
|
| [1] https://github.com/thomasmueller/rubiks/blob/main/README.md
| [2] https://www.json.org/json-en.html
| porridgeraisin wrote:
| > Rubik's cube 3D model
|
| Google had a doodle way back when... That let you play the
| cube on the search page.
|
| I found it hosted here [1] although I'm sure they have a
| doodles archive. Didn't check it myself but it should be
| possible to take the JS from that and use it for our
| purposes.
|
| [1] https://sites.google.com/site/populardoodlegames/rubik-s-
| cub...
| saghm wrote:
| If we're willing optimize for aesthetic over ability to help
| understand, I'll nominate demonstration via Hungarian Folk
| Dance[1] as a candidate for the best medium to depict sorting
| algorithms, which I first saw during a lecture years ago when
| the professor pulled up on of the videos to show us in class
|
| [1]: quicksort is shown here, but the channel has plenty of
| others https://youtu.be/3San3uKKHgg
| aDyslecticCrow wrote:
| Such a internet classic. I have never once searched for it,
| yet seen it dozens of times.
| stevage wrote:
| So what is the best algorithm when you have a bunch of people
| and want them sorted in order of, say, birthday.
| TeMPOraL wrote:
| Tell the people with any CS experience they're not allowed
| to talk, and then let everyone just go for it.
|
| The first part is crucial, because if the group has two or
| more people exposed to CS courses, they'll invariably start
| negotiating the optimal algorithm to use while trying to
| recall the actual implementation, thus preventing any
| actual sorting from taking place.
| lucaslazarus wrote:
| Presumably some kind of Radix Sort: you ask the crowd to
| split up and group together by month, let the people in
| each group self-sort and organize however they'd like, and
| then just concatenate the sorted queues together
| recursivecaveat wrote:
| Real objects are basically always either psuedo-radix
| because you have a good idea of the distribution and aren't
| limited to pairwise comparison, or psuedo-selection because
| the objects are big and heavy so you don't want to move
| them more than necessary. For people self-sorting psuedo-
| radix is definitely the way because they can self-
| parallelize easily.
|
| I say psuedo because real objects have lots of properties
| both on the rearranging and comparison sides that are not
| quite the same as digital ones. For eg it's faster to
| compare numbers that have a large difference in magnitude,
| and it's easier to swap objects that are physically close
| to each other. So following a CS algorithm to the letter is
| usually slower than adapting a little.
| ozgung wrote:
| I've just completed reading all 8 posters on the site. For some
| reason I find them easier to understand than any written
| content, code or math. They are all intuitive. It was fun and
| engaging to solve their notation and meaning they want to
| convey. The one with AVL trees was the most useful to me.
| junga wrote:
| I miss the default IKEA instruction to have two people for
| building even the tiniest piece of furniture.
| QuantumNomad_ wrote:
| How many people do you need to assemble a BILLY bookshelf?
|
| Three!
|
| One to read the manual.
|
| One to be instructed by the first on how assemble it.
|
| One to break up the fight when the first two get into
| fisticuffs over step 4 in the manual.
| kazinator wrote:
| It looks like Step 3 may be using Hoare's original partitioning
| method with two pointers, which is laudable.
| f33d5173 wrote:
| You're misunderstanding. They don't explain how to do
| partitioning at all. Step 3 is just tagging the elements that
| are above the partition element, which there happen to be two
| of.
| tialaramex wrote:
| Well, to the extent a picture can explain they say choose at
| random. That's what the dice shown is about.
|
| A random pivot is... fine. It can't solve the worst case perf
| problem, and it won't ensure high performance for other cases
| either, but hey you did pick a pivot and this algorithm is
| often fast enough.
| f33d5173 wrote:
| I'm talking about step 5. The elements just magically
| migrate to the correct position, whereas in the real
| algorithm they would be moved individually.
| Dan42 wrote:
| This is cool, but missing a LOT of details between steps 4 and 5,
| which is the meat of the quicksort. Actually, the first and last
| elements of step 4 would be swapped, which means the order
| depicted in step 5 is incorrect.
| HarHarVeryFunny wrote:
| Isn't that more of an implementation detail?
|
| I'd guess if you care more about speed than memory it might be
| faster to just move elements into new array - sequence through
| old array appending to start/end of new array according to
| pivot comparison. You'd be moving every element vs leaving some
| in place with a swap approach, but the simplicity of the code &
| branch prediction might win out.
| Dan42 wrote:
| I'm pretty sure the swapping is a fundamental part of the
| quicksort algorithm, not a mere implementation detail. That's
| the reason quicksort is an in-place algorithm.
| Dan42 wrote:
| Actually you're right, it _is_ an implementation detail.
| The original isn't mistaken, it's just showing the lo-to-hi
| partitioning pass rather than the from-both-ends version I
| had in mind when I implemented quicksort before.
|
| shame, shame, I should have double-checked before posting.
| LordGrey wrote:
| Step #5 is very much a "draw the rest of the fucking owl" step.
| rfl890 wrote:
| I ignored the arrows and interpreted it as "move all elements
| lower than the marker in order to the left of the marker, and
| move all elements higher than the marker in order to the right
| of the marker". It's not clear, but if you use a bit of
| intuition you can come to this conclusion. Personally it took
| me about 5 seconds.
| xandrius wrote:
| Have you ever learnt about Quicksort? If so, it might give
| you an edge on what to expect.
| imajoredinecon wrote:
| I agree it does a pretty good job of communicating that. I
| think the other commenters are pointing out that doesn't show
| _how_ to efficiently get all the smaller items left of the
| partition and larger ones to the right. While that's probably
| second nature to most people who've taken an algorithms class
| or done a decent amount of programming, I guess it's up for
| interpretation how obvious it would be to the "intended
| audience" of the ikea manual
| tialaramex wrote:
| I can't tell if this was serious. This really is how a pure
| Quicksort works, you just recursively apply this same algorithm
| and the result is sorted. In contrast the initial circles
| approach can't be recursed to draw the rest of the fucking owl.
| koolba wrote:
| Step 4 is that one step you have to move all the pieces around
| repeatedly to match the paper until you realize one them is
| upside down and the other side is lightly sanded.
| BaardFigur wrote:
| Don't call it quicksort (aka quicksort/quicksoert). It's so
| jarring to read. It's pronounced line the vocal sound in "learn"
| TeMPOraL wrote:
| Doesn't matter - it's just a FEJKA manual anyway.
| QuantumNomad_ wrote:
| But it does matter. I'm not sure if you are already aware and
| did it intentionally or if it was a happy accident, but FEJKA
| really is named that because it's a real word in Swedish that
| comes from English with meaning very near to how you used it
| there.
|
| Swedish adjective "fejk" comes from English adjective "fake".
|
| Swedish "fejka" is the verb form of the same, with the
| meaning similar to one of the English meanings of the verb
| form: To give the impression that something is a certain way
| when it is not.
|
| And that's what the FEJKA series of products happen to be.
| Artificial plants that look like they are real, even though
| they are not :)
|
| And so back to the point of naming these pretend IKEA
| manuals. If they are to really look real without being real,
| they should be named in a way that would make even swedes
| second guess whether they _might_ be real manuals. (When seen
| in a context where it was not immediately stated that they
| are imitations.)
| TeMPOraL wrote:
| > _I'm not sure if you are already aware and did it
| intentionally or if it was a happy accident, but FEJKA
| really is named that because it's a real word in Swedish
| that comes from English with meaning very near to how you
| used it there._
|
| I guessed as much; I'm Polish but know enough English that
| I burst into laughter when I first saw a fake plant labeled
| FEJKA in a local IKEA store. In fact, I couldn't believe
| they'd be this direct with naming. But then I don't know
| enough Swedish to translate the other names.
|
| (Still wonder what kind of geopolitical order they meant
| when they named their wardrobe system PAX. Or is it just
| because you can _pack_ absurd amount of things into it?)
|
| > _If they are to really look real without being real, they
| should be named in a way that would make even swedes second
| guess whether they might be real manuals. (When seen in a
| context where it was not immediately stated that they are
| imitations.)_
|
| Fair enough. I was just making an unsophisticated joke
| about the FEJKA line :).
| pmarreck wrote:
| Brilliant. Never heard of this site.
| bobsmooth wrote:
| I love this, it's so adorable.
| bigswede wrote:
| Nice! KVICK SART, would be the most correct swenglish title
| though.
| CyberDildonics wrote:
| I think a much better explanation would be to just say that it
| partitions the values into a lower and higher half. Then it
| recursively does the same thing to each half.
|
| After that you just have to understand exactly how partitioning
| works and get the ranges correct.
| theogravity wrote:
| This surprisingly made this easy to remember for me.
|
| Unfortunately, the merge sort instructions doesn't make sense to
| me, specifically step 3.
| jfengel wrote:
| It's not a merge sort, it's just a partition. Mark every
| element greater than your pivot as "move right". Then step 4
| marks every smaller element as "move left". Step 5 actually
| does that.
|
| You don't really need to split that into 3 steps, though it
| looks a bit more like a real IKEA diagram with the extra steps.
| stabbles wrote:
| It should be possible to better explain in IKEA style how to
| perform partitioning with swapping. In its current form it can
| make people fall into a quadratic complexity trap.
| Awesomedonut wrote:
| Oh my goodness, I'm in love with this site! One of my favourite
| things about HN is all of the cool sites I discover through the
| community :D
| Daunk wrote:
| Seeing a random O hurts my Swedish brain. Especially when "Sort"
| is Swedish already.
| cnxhk wrote:
| I am wondering if we could use any llm to generate similar graphs
| lol.
___________________________________________________________________
(page generated 2025-09-24 23:00 UTC)