[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