pivot

The item quicksort chooses to split a list around: smaller items go to its left and larger ones to its right.

In more detail

After partitioning, the pivot is in its final sorted position. A pivot near the median splits the work evenly; one near the minimum or maximum leaves one side almost empty and drives quicksort towards O(n^2). Choosing the pivot at random makes that worst case very unlikely for any input.

Related terms

Taught in

References