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.