Quick Sort

Spotting one

You need to sort without extra room. Or, far more common in practice, you need the kth largest or smallest item and do not actually need everything sorted.

That second case has its own name, quickselect, and it is the reason this is worth learning properly.

The idea, plainly

Pick one item, the pivot. Move everything smaller to its left and everything bigger to its right. The pivot is now exactly where it belongs, and you repeat on each side.

Quickselect is the same with one change that makes all the difference. After partitioning you know which side your answer is on, so you only repeat on that side and throw the other away.

Where to start

Partition Array According to a Pivot Value first. Partitioning is the method. Get it right on its own.

Sort an Array next, wrapping the recursion around it.

Then Kth Largest Element in an Array, where quickselect earns its keep. Find the Kth Largest Integer in the Array is the same idea with a custom comparison, where longer number strings count as larger and equal length ones compare normally.

Wiggle Sort II is the hardest here and combines finding the middle value with a careful rearrangement.

Common mistakes

Always taking the first or last item as the pivot. On already sorted input that is the worst possible choice and the whole thing crawls. Pick at random, or take the middle of three.

Recursing into both sides during quickselect. That is just a full sort again and the entire advantage disappears.

Off-by-one errors in the partition that drop or duplicate the pivot. Sorting a few tiny arrays by hand is the fastest way to find these.

Expecting equal items to stay in their original order. They will not.