Structure: Separate list into the ``lows'' and ``highs.'' Put the ``lows'' in the left section of the array and the ``highs'' in the right. Sort each recursively. Resulting list is definitely sorted.
Tricky part: How separate list?
Selection sort is a special case in which we define the ``highs'' to be a set of size 1 and the lows all the rest.
Idea: We choose an element in the list to be the ``pivot.'' Easy to create two sublists from this, depending on which side of the pivot we're on. Animated example. This involves constant work per element, because we simply check each one and then stow it away according to whether it's bigger or smaller than the pivot.
The partitioning procedure is especially elegant because it can be done in place.
Awkwardness: Hard to pick a good pivot fast.
