[shib71]

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.

[nucleardog]

> 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!

[ksenzee]

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.

[photon_lines]

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...

[yifanl]

The Fenwick tree in your cheat sheet seems a little broken

[photon_lines]

Can you go into a little more detail? What is broken exactly?

[yifanl]

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).

[crdrost]

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.

[ants_everywhere]

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.

[eru]

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.

[xigoi]

What you’re describing is more like MSD radix sort.

[crdrost]

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.

[moi2388]

That’s how I sorted cards long before knowing about sorting algorithms

[adastra22]

Sounds like they captured the IKEA manual experience very well!