quicksort

A divide-and-conquer sort that picks a pivot, partitions the items into those smaller and larger than it, and sorts each part recursively.

In more detail

Quicksort averages O(n log n) and sorts in place, which makes it fast in practice. A consistently bad pivot, such as the last element of already sorted input, makes it O(n^2). It is not stable by default.

Related terms

Taught in

References