Quick sort visualizer

Type a list in the box, separated by commas, spaces or new lines. Numbers are sorted by value and words alphabetically, ignoring capitals. The sorted list appears straight away, and the animation below plays the sort one step at a time, up to 24 items.

Play, Step forward, Step back and Speed control the animation, and the key under the bars says what each colour means. Show the steps lists every pivot and where it landed.

Quick sort picks one item as the pivot; this version uses the last item in the stretch it's sorting. It walks through the rest, moving everything smaller than the pivot to the left side. Then it puts the pivot just after those smaller items. The pivot is now in its final place, with everything smaller on its left and everything else on its right.

Then it does the same to the left side and the right side separately, each with a pivot of its own, until every stretch is a single item.

On average quick sort makes on the order of n log n comparisons, like merge sort, and in practice it's often faster. But its worst case is n², and with the last item as pivot that worst case is a list that's already sorted: every pivot is the biggest item, so each split peels off just one item. The comparison table on the sorting algorithms page shows the sorted and reversed lists costing 45 comparisons each, against 23 for a shuffled one.

Real implementations dodge this by choosing the pivot more carefully, for example the middle of three items or a random one.

Tony Hoare developed quicksort in 1959, as a visiting student at Moscow State University, and published it in 1961. He was working on machine translation and needed to sort the words of Russian sentences before looking them up in a Russian-English dictionary kept in alphabetical order on magnetic tape.