Quicksort

How splitting a list around one number ends up sorting all of it

Quicksort picks one element, the pivot, and partitions the list: smaller elements go to its left, larger ones to its right. The pivot is now in its final place, and quicksort recurses on each side.

Take [7, 2, 9, 4, 1, 8, 5] with pivot 5. Partitioning gives [2, 4, 1] 5 [7, 9, 8], which fixes 5 at index 3. Each side is sorted the same way until every piece has one element or none.

Partitioning works in place: it swaps elements within the array, with no second copy. Merge sort does its work after recursing, but quicksort does it before, so there is nothing to merge at the end.

Quicksort

Java's Arrays.sort sorts numbers with a dual-pivot quicksort

Since Java 7, calling Arrays.sort on an int or double array runs dual-pivot quicksort. It picks two pivots and splits the array into three parts: below the first pivot, between the two, and above the second.

Other libraries use quicksort hybrids too. C++ std::sort is usually introsort, which switches to heapsort if the recursion gets too deep. Go's sort package has used pdqsort, a quicksort variant, since Go 1.19.

Quicksort

Each split pins one number in place, so nothing needs merging

Partitioning n items costs about n comparisons, one per item. If pivots land near the middle, the pieces halve at each level. That gives about log₂ n levels and n log₂ n work, done in place with scans that suit CPU caches.

A bad pivot ruins this. On a sorted list, picking the first element as pivot peels off one item per split, which means n levels and about n²/2 comparisons. Random or median-of-three pivots make such splits very unlikely.