Quicksort sorts by choosing a pivot, partitioning the remaining elements around it, and recursively sorting the resulting regions.

A partition step rearranges the data so that elements on one side belong before the pivot and elements on the other side belong after it according to the chosen ordering.

If partitions are reasonably balanced, the running time is typically

$$O(n\log n).$$

If each pivot produces a highly unbalanced split, the worst case becomes

$$O(n^2).$$

Randomized or carefully chosen pivots reduce the chance of repeatedly poor partitions.

Quicksort is usually implemented in place and often has good locality. Unlike merge sort, its key divide-and-conquer work occurs mainly during the divide step: partitioning organizes the data before the recursive calls.