My first thought was that it would be explaining Quicksort using an Ikea warehouse as a metaphor, to show how different algorithms suit different constraints.
As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice. It took some work for me to understand the diagram, and I've used Quicksort.
> As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice.
I have no formal CS background or education at all, but have been working in IT for... over 20 years now?
So I'm not a "novice" in one sense, but in another my education on "algorithms" is pretty light and mostly through osmosis. Quicksort specifically is something where I've looked at the Wikipedia article on a number of times to understand but never managed to grasp.
The diagram made it click for me pretty much immediately. Yesterday if you asked me to implement a quicksort I wouldn't have had any idea where to begin, today I can say pretty confidently that I could implement something that would give you back a sorted list.
I'm probably an outlier here--minimal algorithms background, but an intuitive comfort with things like recursion--but at least some anecdotal evidence that it _may_ be useful to a novice!
If you’re an outlier, I’m out there with you: I’ve also been writing software professionally for 20 years, I have no CS degree, and I’m not fool enough to reimplement algorithms like quicksort that are sitting right there in stdlib. I similarly found this explanation a lot more useful than anything else I have read about quicksort, and I’m confident I could implement it now, but couldn’t have before I read this.
If you guys like visual-explanations that are a bit more intuitive -- I put actually made guides on both data-structures and algorithms not too long ago which you can find here:
The visual is extremely hard to understand how it relates to the description, given that it looks to be 1-indexed, but the description only makes sense for 0-indexing (4th element stores the sum of the first 4 elements), not to mention none of the binary indexes seem to be storing the correct sums (or they're storing sums of a tree that isn't being presented).
The visual is directly from here (I recommend you give it a read if you want to grasp the full intuition on how a Fenwick tree works (page 97)): https://cses.fi/book/book.pdf
I should have included the full visuals which are included there and I can see your point on why people would get confused by that visual - so I'll make a note to include the full image when I have more time. Thank you for the feedback.
For me the key was just application to figuring out if any cards are missing in a deck by sorting it.
Assume spades < clubs < diamonds < hearts, and ascending order for cards for all suits. Once you know the principle you can switch to US playing card order if you want.
In your first pass, divide the deck into black and red cards. Then divide black into spades and clubs. Then divide spades into <= 7 and >7. Then insertion sort the cards <= 7, then insertion sort the cards > 7, spades are now sorted. Clubs come next, divide into <= 7 and > 7, insertion sort, and combine. Split diamonds and hearts, repeat with diamonds, repeat with hearts.
“What about the pivot thing?” Well, that's because we don't know the midpoint of our set in a typical sort. So instead you can just grab a random card and then go through the deck to find all cards < that card. If you want slightly fewer passes, use median of three.
Similary idea: I used to be a TA and every week I would sort ~50 papers or exams alphabetically to make it easier to verify accuracy in the grading spreadsheet. Sorting this many papers regularly forces you to find a good way to do it, and it's hard to avoid recursion.
Even better: sort something physically large like several bookshelves of books or a record collection. You can't hold the collection in your hand and you're forced to use piles. You may even decide to work bookshelf by bookshelf first.
These are all good ways to develop intuition for sorting algorithms. Personally I always just use quicksort until I've come to a part of the alphabet where I can immediately recall which letter precedes every other then I do insertion sort. You might decide to use another hybrid sort like timsort.
A lot of people have trouble with understanding recursion. Perhaps that's where they struggle with quicksort?
Luckily, there's a simple non-recursive quicksort variation. It goes like this:
Simplifying assumption: all items are distinct.
Invariant: Throughout our procedure, we will have a bunch of bags arranged in a sequence before us from left to right. Items in a bag are all jumbled up, but all items in bag A are smaller than any item in bag B, if A comes before B in our sequence.
Now, we start by stuffing all our items into a single bag.
We repeat the following:
- Pick an arbitrary bag X. Anyone will do, you can pick at random, or your favourite bag, or always the left-most or whatever. Only one condition: bag X has to have more than a single element left in it.
- Grab a random element E out of X as your pivot.
- Categories all elements of X into: smaller than E, E itself, and bigger than E. Stick these categories into their own bags and place them into our sequence in the appropriate order.
Repeat until all bags left have one or fewer elements.
So binary MSD radix sort is also just called "binary quicksort" by some authors; they are substantially the same algorithm. How can I explain?
If you really want to replicate the exact swaps and pivoting in the most common form of quicksort, what your fingers will actually do, looks like this.
1. Cut the to-be-sorted deck-portion in half so that you can peek at the first, last, and middle card. Choose the median and swap it to the back of the deck.
2. The deck now sits in your left hand and your right hand conceptually contains two empty stacks of cards, the one between thumb and forefinger is a stack <= to pivot, and between forefinger and ring finger is the stack > pivot.
3. You are permitted two operations: (a) deal a card > pivot from the left hand onto the back of the second stack, or (b) deal a card <= pivot from the left hand onto the back of the first stack, but to make it a conceptual swap you now have to pick the card from the top of the second stack and put it on the back of the second stack.
4. Process the whole left hand this way; at the end the pivot you selected will be at the back of the first stack in your right hand. Separate it out and recurse on the two remaining stacks.
So if you do this enough you'll start to appreciate these two things:
- "with cards I don't really need to rotate that second stack card by card whenever I add to that first stack -- that's not affecting correctness, it's just needed for array sorts to be in-place"
and similarly
- "with cards I sometimes get these really stupid starts where like the median is 10 of spades and I'm going to split this like 9-1-42, eff it I'm just going to pretend that the median was the king of clubs, that's what I needed to split the damn deck in half."
and those are the optimizations performed in the above description of quicksort.
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.
They are until you hit one for something that is so simple it does not really need instructions, then you will end up in a tail spin! We bought a window shade puller thing and it had instructions!
Lego are also superb at instructions, for obvious reasons. I've put together a couple of modern Lego models with a lot of pieces and they are still as good as I remember 40+ years ago. I have to say that the model of the Chinese Year of the Dragon beastie from 2024? was pretty tricky.
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.
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.
> 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.
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...
The name feels like such a near miss though... Kvick (beyond being my surname) does mean quick and I see they changed to it from kwick to make the title "more Swedish". Great! But sört? That's not a Swedish word and feels very "trying to seem Swedish without knowing any Swedish". That letter would be pronounced somewhat like the u in blur.
Meanwhile sort in Swedish is sortera. Sort itself does mean sort as in kind/type. So perhaps Kvick Sort would be the best version of the name?
IKEA-fication of terms in other languages (although on the general internet that tends to converge mostly on English) is a long standing meme. It's not supposed to be swedish, it's not even supposed to sound strictly swedish, it's supposed to sound and look ikea-ish
I understand where you're coming from. From the perspective of someone with no knowledge of Swedish that's a clear distinction.
From my perspective as a Swede, however, making it sound Swedish is the same as making it sound Ikea-ish. Because Ikea products all have names which are either Swedish words or typical Swedish names.
I am French and our language is also often abused for fun. I find it funny as well and I am actually quite glad that it makes it on the meme-o-meter because it means it is popular.
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
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.
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.
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
Or to make “concatenate” more physical, divide an area into 12, one for each month in order, then in each area, people sort themselves.
This is similar to the best design we have for the fastest way to board a plane: take people in a dozen or so “chunks”, then have each chunk stand in a sorting area atop a diagram of the airplane, one chunk at a time. A group enters the area and sorts themselves by standing near the place on the diagram where their seat is, then boards the plane in line. As each chunk boards, they’re already in the right order so that nobody is blocking anyone while trying to stuff their overhead luggage.
I’m not sure if any company has implemented the system but there was some test a company did of a bunch of boarding techniques and it was the most efficient.
It should be obvious that's most efficient if you can get everyone to be there 30 mins early. Which they can't, mostly due to connecting flights and really not having what to do at the gate for 30 mins.
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.
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.
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.
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.
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.
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.
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.
I kind of get it, but just like Ikea instructions, you start second guessing yourself, then you realize, its BACKWARDS after you flip back 5 pages in when something doesn't fit.
Are you on about the ones where the bottom is carboard that could go either way? LOL I hate building those.
Ikea instructions are like an Easy to Medium level test in reverse engineering skills, with occasional EXPERT TIER SUPREME level skills needed because of subtleties.
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.
I'm a programmer (after a fashion) but I don't know how quicksort works.
This is how I understand it after reading these instructiöns, 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 :)
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.
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.
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.
this page is fun. and it has a large number of algorithms "explained" Ikea style.
I think it's great to explain them to others. I think it doesn't work as a teaching tool per se. it needs someone who understands the algorithms already, to decide and explain what's going on.
I think sort would be even better because it's less Swenglish. It's the base for sorting in Swedish (sortera) after all. Sört does really bother me since it sounds so wrong (almost like the u in blur). Sårt use closer to how Swedes would pronounce the English word sort, that's true.
At least they changed the first word to Kvick because it means the right thing and sounds about right. And it happens to be my family name.
The key to step 3 (of the merge sort) is the little nx in the middle that tells you to repeat step 3 n times. Each time, you take a right or left branch based on if the new weight from the half plank is lighter or heavier than the current weight.
You also have to understand that step 1 means you recursively merge sort each half before you merge the two sorted halves.
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.
I was confused by step (3). The right pillar doesn't need to move right because it's already to the right of the chosen pillar.
I guess what it's trying to say is just "mark it as needing to be to the right", and then do the opposite in (4) and then (5) is where things actually move.
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.)
> 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 :).
I never understood why use Quick Sort when you could use something else instead, like Merge Sort. Using a pivot seems backwards compared to something guaranteed to be NLOGN time.
Worst case is n^2, where the chosen element is either the largest or the smallest element. Then the result is an insertion sort across the whole list. (Not sure if the order would matters, don't remember off the top of my head).
Do people actually find IKEA explanations helpful?
I always thought they were a cost-cutting measure to avoid text in different languages. For me, they tend to be incomprehensible. Maybe because I have a very verbal style of learning, but I think it's not only that because I do find Lego instructions easy.
This captured the IKEA experience perfectly in the sense that I can understand it because I already know Quicksort, but otherwise, I don't think I would figure it out.
IKEA instructions are kinda like a worse version of Lego instructions. But in general I could not imagine assembling a 3d shape without pictures/drawings. Using text instructions for 3d shapes sounds like a nightmare.
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.
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.
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.
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
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.
It kind of annoys me when people just adds diacritics to fake swedish/ikea names. They are not for decoration, but makes it a completely different sound.
How about the direct translation “snabbsortering”? Or even “kvicksortering”, to more resemble the original? Both are perfectly valid swedish.
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.
You use a value called a pivot, not a weight, and there are many ways and endless variations you can read about, including just choosing a random value from the current range.
My first thought was that it would be explaining Quicksort using an Ikea warehouse as a metaphor, to show how different algorithms suit different constraints.
As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice. It took some work for me to understand the diagram, and I've used Quicksort.
> As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice.
I have no formal CS background or education at all, but have been working in IT for... over 20 years now?
So I'm not a "novice" in one sense, but in another my education on "algorithms" is pretty light and mostly through osmosis. Quicksort specifically is something where I've looked at the Wikipedia article on a number of times to understand but never managed to grasp.
The diagram made it click for me pretty much immediately. Yesterday if you asked me to implement a quicksort I wouldn't have had any idea where to begin, today I can say pretty confidently that I could implement something that would give you back a sorted list.
I'm probably an outlier here--minimal algorithms background, but an intuitive comfort with things like recursion--but at least some anecdotal evidence that it _may_ be useful to a novice!
If you’re an outlier, I’m out there with you: I’ve also been writing software professionally for 20 years, I have no CS degree, and I’m not fool enough to reimplement algorithms like quicksort that are sitting right there in stdlib. I similarly found this explanation a lot more useful than anything else I have read about quicksort, and I’m confident I could implement it now, but couldn’t have before I read this.
If you guys like visual-explanations that are a bit more intuitive -- I put actually made guides on both data-structures and algorithms not too long ago which you can find here:
Visual-Focused Algorithms Cheat Sheet — https://photonlines.substack.com/p/visual-focused-algorithms...
Visual Data Structures Cheat Sheet — https://photonlines.substack.com/p/visual-data-structures-ch...
The Fenwick tree in your cheat sheet seems a little broken
Can you go into a little more detail? What is broken exactly?
The visual is extremely hard to understand how it relates to the description, given that it looks to be 1-indexed, but the description only makes sense for 0-indexing (4th element stores the sum of the first 4 elements), not to mention none of the binary indexes seem to be storing the correct sums (or they're storing sums of a tree that isn't being presented).
The visual is directly from here (I recommend you give it a read if you want to grasp the full intuition on how a Fenwick tree works (page 97)): https://cses.fi/book/book.pdf
I should have included the full visuals which are included there and I can see your point on why people would get confused by that visual - so I'll make a note to include the full image when I have more time. Thank you for the feedback.
For me the key was just application to figuring out if any cards are missing in a deck by sorting it.
Assume spades < clubs < diamonds < hearts, and ascending order for cards for all suits. Once you know the principle you can switch to US playing card order if you want.
In your first pass, divide the deck into black and red cards. Then divide black into spades and clubs. Then divide spades into <= 7 and >7. Then insertion sort the cards <= 7, then insertion sort the cards > 7, spades are now sorted. Clubs come next, divide into <= 7 and > 7, insertion sort, and combine. Split diamonds and hearts, repeat with diamonds, repeat with hearts.
“What about the pivot thing?” Well, that's because we don't know the midpoint of our set in a typical sort. So instead you can just grab a random card and then go through the deck to find all cards < that card. If you want slightly fewer passes, use median of three.
Similary idea: I used to be a TA and every week I would sort ~50 papers or exams alphabetically to make it easier to verify accuracy in the grading spreadsheet. Sorting this many papers regularly forces you to find a good way to do it, and it's hard to avoid recursion.
Even better: sort something physically large like several bookshelves of books or a record collection. You can't hold the collection in your hand and you're forced to use piles. You may even decide to work bookshelf by bookshelf first.
These are all good ways to develop intuition for sorting algorithms. Personally I always just use quicksort until I've come to a part of the alphabet where I can immediately recall which letter precedes every other then I do insertion sort. You might decide to use another hybrid sort like timsort.
A lot of people have trouble with understanding recursion. Perhaps that's where they struggle with quicksort?
Luckily, there's a simple non-recursive quicksort variation. It goes like this:
Simplifying assumption: all items are distinct.
Invariant: Throughout our procedure, we will have a bunch of bags arranged in a sequence before us from left to right. Items in a bag are all jumbled up, but all items in bag A are smaller than any item in bag B, if A comes before B in our sequence.
Now, we start by stuffing all our items into a single bag.
We repeat the following:
- Pick an arbitrary bag X. Anyone will do, you can pick at random, or your favourite bag, or always the left-most or whatever. Only one condition: bag X has to have more than a single element left in it.
- Grab a random element E out of X as your pivot.
- Categories all elements of X into: smaller than E, E itself, and bigger than E. Stick these categories into their own bags and place them into our sequence in the appropriate order.
Repeat until all bags left have one or fewer elements.
What you’re describing is more like MSD radix sort.
So binary MSD radix sort is also just called "binary quicksort" by some authors; they are substantially the same algorithm. How can I explain?
If you really want to replicate the exact swaps and pivoting in the most common form of quicksort, what your fingers will actually do, looks like this.
1. Cut the to-be-sorted deck-portion in half so that you can peek at the first, last, and middle card. Choose the median and swap it to the back of the deck.
2. The deck now sits in your left hand and your right hand conceptually contains two empty stacks of cards, the one between thumb and forefinger is a stack <= to pivot, and between forefinger and ring finger is the stack > pivot.
3. You are permitted two operations: (a) deal a card > pivot from the left hand onto the back of the second stack, or (b) deal a card <= pivot from the left hand onto the back of the first stack, but to make it a conceptual swap you now have to pick the card from the top of the second stack and put it on the back of the second stack.
4. Process the whole left hand this way; at the end the pivot you selected will be at the back of the first stack in your right hand. Separate it out and recurse on the two remaining stacks.
So if you do this enough you'll start to appreciate these two things:
- "with cards I don't really need to rotate that second stack card by card whenever I add to that first stack -- that's not affecting correctness, it's just needed for array sorts to be in-place"
and similarly
- "with cards I sometimes get these really stupid starts where like the median is 10 of spades and I'm going to split this like 9-1-42, eff it I'm just going to pretend that the median was the king of clubs, that's what I needed to split the damn deck in half."
and those are the optimizations performed in the above description of quicksort.
That’s how I sorted cards long before knowing about sorting algorithms
Sounds like they captured the IKEA manual experience very well!
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
"I agree, IKEA instructions are great"
They are until you hit one for something that is so simple it does not really need instructions, then you will end up in a tail spin! We bought a window shade puller thing and it had instructions!
Lego are also superb at instructions, for obvious reasons. I've put together a couple of modern Lego models with a lot of pieces and they are still as good as I remember 40+ years ago. I have to say that the model of the Chinese Year of the Dragon beastie from 2024? was pretty tricky.
SQLite also has lots of excellent railroad diagrams for SQL syntax. e.g. https://sqlite.org/lang_select.html#overview
> 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...
> I'm sure they have a doodles archive
You are correct: https://doodles.google/
It doesn't seem to have the Rubik's cube, though
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.
> 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.
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.
> Because the recursive implementation is surprisingly straightforward and concise
It's also technically not quicksort
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)?
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...
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).
> since for some reason in FP languages quicksort is typically next after "hello world"
How does FP handle the random selection?
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.)
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
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)
Just do the Sedgewick thing and take the median of the first, middle, and last elements.
Quicksort in FP?
Surely you mean mergesort, that's the classic FP sorting example.
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
It really shines if you want a shortcut on a whiteboard interview, though.
Step six: draw the rest of the fucking owl.
Yeah this is lousy. This wouldn’t teach anyone anything.
This was actually a really neat refresher.
The name feels like such a near miss though... Kvick (beyond being my surname) does mean quick and I see they changed to it from kwick to make the title "more Swedish". Great! But sört? That's not a Swedish word and feels very "trying to seem Swedish without knowing any Swedish". That letter would be pronounced somewhat like the u in blur.
Meanwhile sort in Swedish is sortera. Sort itself does mean sort as in kind/type. So perhaps Kvick Sort would be the best version of the name?
I think Kvik Ordning would be more IKEA
Yes, this sounds great and very Ikea.
Snabb Sortera
IKEA-fication of terms in other languages (although on the general internet that tends to converge mostly on English) is a long standing meme. It's not supposed to be swedish, it's not even supposed to sound strictly swedish, it's supposed to sound and look ikea-ish
I understand where you're coming from. From the perspective of someone with no knowledge of Swedish that's a clear distinction.
From my perspective as a Swede, however, making it sound Swedish is the same as making it sound Ikea-ish. Because Ikea products all have names which are either Swedish words or typical Swedish names.
I am French and our language is also often abused for fun. I find it funny as well and I am actually quite glad that it makes it on the meme-o-meter because it means it is popular.
You rarely hear fun things about, say, Finnish.
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
Such a internet classic. I have never once searched for it, yet seen it dozens of times.
So what is the best algorithm when you have a bunch of people and want them sorted in order of, say, birthday.
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.
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.
Tell them to make sure the person in front of them has a birthday before theirs. If not, keep jumping back the line until they do.
Practical CS theory isn’t really relevant here because it is N-parallel for N people.
You could use a sorting network too
That is, in practice, what I just described.
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
Or to make “concatenate” more physical, divide an area into 12, one for each month in order, then in each area, people sort themselves.
This is similar to the best design we have for the fastest way to board a plane: take people in a dozen or so “chunks”, then have each chunk stand in a sorting area atop a diagram of the airplane, one chunk at a time. A group enters the area and sorts themselves by standing near the place on the diagram where their seat is, then boards the plane in line. As each chunk boards, they’re already in the right order so that nobody is blocking anyone while trying to stuff their overhead luggage.
I’m not sure if any company has implemented the system but there was some test a company did of a bunch of boarding techniques and it was the most efficient.
It should be obvious that's most efficient if you can get everyone to be there 30 mins early. Which they can't, mostly due to connecting flights and really not having what to do at the gate for 30 mins.
I was disappointed that men in the video were sorted by their numbers, but not their height! ;)
Hello everyone! Author of IDEA here - great to hear that this has caught some attention.
As it happens, these instructions were developed in the course of a 1st-year undergraduate course, so it's tried and tested in teaching noobs.
There is even a song-and-dance version (sorry, German lyrics): https://youtu.be/iq_TcSvWaY4
Cheers, Sándor Fekete, Professor for Algorithmics, TU Braunschweig https://www.ibr.cs.tu-bs.de/users/fekete/
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.
Also checked the PDF compilation and it is a surprisingly effective way to explain algorithms considering there are no words at all.
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.
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.
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.
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.
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
"Bublé Sort": Animated GIF explanation of bubble sort using tracks from Michael Bublé's 'Let It Snow!' album
https://communities.sas.com/t5/Graphics-Programming/Fun-With...
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.
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.
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.
BINÄRY SEARCH has you covered. (-:
* https://idea-instructions.com/binary-search/
The second page is borderline incomprehensible, I'm not sure I would ever understand what it's trying to say if I didn't already know.
Stuck in second round of step 2, since there is no middle cup to lift!
I kind of get it, but just like Ikea instructions, you start second guessing yourself, then you realize, its BACKWARDS after you flip back 5 pages in when something doesn't fit.
Reminds me of when I was assembling some drawers and put in the bottom of one upside-down. At least I wasn't the one using them...
Are you on about the ones where the bottom is carboard that could go either way? LOL I hate building those.
Ikea instructions are like an Easy to Medium level test in reverse engineering skills, with occasional EXPERT TIER SUPREME level skills needed because of subtleties.
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
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.
I'm a programmer (after a fashion) but I don't know how quicksort works.
This is how I understand it after reading these instructiöns, 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 :)
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).
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.
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.
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.
this page is fun. and it has a large number of algorithms "explained" Ikea style.
I think it's great to explain them to others. I think it doesn't work as a teaching tool per se. it needs someone who understands the algorithms already, to decide and explain what's going on.
thank you for sharing
Nice! KVICK SÅRT, would be the most correct swenglish title though.
I think sort would be even better because it's less Swenglish. It's the base for sorting in Swedish (sortera) after all. Sört does really bother me since it sounds so wrong (almost like the u in blur). Sårt use closer to how Swedes would pronounce the English word sort, that's true.
At least they changed the first word to Kvick because it means the right thing and sounds about right. And it happens to be my family name.
Or there's quick sort in Hungarian dance if you prefer
Quick sort with Hungarian, folk dance
https://www.youtube.com/watch?v=3San3uKKHgg
Why am I disappointed they didn’t sort the dancers by height? Very cool demo.
This surprisingly made this easy to remember for me.
Unfortunately, the merge sort instructions doesn't make sense to me, specifically step 3.
The key to step 3 (of the merge sort) is the little nx in the middle that tells you to repeat step 3 n times. Each time, you take a right or left branch based on if the new weight from the half plank is lighter or heavier than the current weight. You also have to understand that step 1 means you recursively merge sort each half before you merge the two sorted halves.
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.
Wrong diagram - “merge sort”.
I was confused by step (3). The right pillar doesn't need to move right because it's already to the right of the chosen pillar.
I guess what it's trying to say is just "mark it as needing to be to the right", and then do the opposite in (4) and then (5) is where things actually move.
Don't call it quicksört (aka quicksørt/quicksœrt). It's so jarring to read. It's pronounced line the vocal sound in "learn"
Doesn't matter - it's just a FEJKA manual anyway.
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.)
> 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 :).
I miss the default IKEA instruction to have two people for building even the tiniest piece of furniture.
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.
I never understood why use Quick Sort when you could use something else instead, like Merge Sort. Using a pivot seems backwards compared to something guaranteed to be NLOGN time.
here you go:
https://idea-instructions.com/merge-sort/
and I think in this discussion we marvel the presentation, not the algorithm per se.
Quick sort can be done in place
Merge sort requires additional space
> Choosing the dividing element at random is a good strategy to avoid bad worst-case runtime.
Please can someone explain what’s meant by “bad worse-case runtime”?
Worst case is n^2, where the chosen element is either the largest or the smallest element. Then the result is an insertion sort across the whole list. (Not sure if the order would matters, don't remember off the top of my head).
Do people actually find IKEA explanations helpful?
I always thought they were a cost-cutting measure to avoid text in different languages. For me, they tend to be incomprehensible. Maybe because I have a very verbal style of learning, but I think it's not only that because I do find Lego instructions easy.
This captured the IKEA experience perfectly in the sense that I can understand it because I already know Quicksort, but otherwise, I don't think I would figure it out.
Funny. I have always found their instructions great. I am quite visual.
IKEA instructions are kinda like a worse version of Lego instructions. But in general I could not imagine assembling a 3d shape without pictures/drawings. Using text instructions for 3d shapes sounds like a nightmare.
Not saying 100% pure text instructions without images would make sense, but for me, some text alongside the drawings would help immensely.
I've tried to have AI generate these types of visual instructions from text without luck. Perhaps it was the IKEA-style guide I needed.
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
It looks like Step 3 may be using Hoare's original partitioning method with two pointers, which is laudable.
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.
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.
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.
The curly braces with the arrow pointing down are the thing implying the recursive calls on that set of elements until you’re done.
you're describing step 6
It would be clearer if they weren't magically sorted early. Maybe they can improve in a later edition of the instructions.
I think maybe Lego would cut away to show one layer of repetition for example.
Step #5 is very much a "draw the rest of the fucking owl" step.
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.
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
Have you ever learnt about Quicksort? If so, it might give you an edge on what to expect.
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.
[dead]
It kind of annoys me when people just adds diacritics to fake swedish/ikea names. They are not for decoration, but makes it a completely different sound.
How about the direct translation “snabbsortering”? Or even “kvicksortering”, to more resemble the original? Both are perfectly valid swedish.
Ikea instructions are great because they explain something simple. That's pretty hard to do it wrong in the first place.
Brilliant. Never heard of this site.
The recursion element should be a reproduction of the entire IKEA instruction in miniature
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.
How do you decide which weight to use to create two halves?
In their example they choose a random pivot, is that what you're asking about?
There are a number of strategies but random will indeed work and is simple to explain.
You use a value called a pivot, not a weight, and there are many ways and endless variations you can read about, including just choosing a random value from the current range.
I love this, it's so adorable.
I hate quick sort.
merge sort has a better big O, is cleaner conceptually, and is trivial to run concurrently.
bah humbug
main disni auto cuan jo777.help
I am wondering if we could use any llm to generate similar graphs lol.
I have use nano banana to generate some like this https://postimg.cc/PN0Z1vz2
Seeing a random Ö hurts my Swedish brain. Especially when "Sort" is Swedish already.
It's a https://en.wikipedia.org/wiki/Metal_umlaut