Quicksort
Quicksort is a divide and conquer sorting algorithm that works in place. It picks a pivot element, partitions the array so smaller values land left and larger values land right, then recursively sorts each side.
Partitioning
The heart of quicksort is the partition step. Choose a pivot, then rearrange the array so every element less than the pivot comes before it and every greater element comes after. After partitioning, the pivot sits in its final sorted position, and the two sides are sorted independently.
Performance
On average quicksort runs in linearithmic time and is very cache friendly, often beating other sorts in practice. But a poor pivot, such as always choosing the first element on already sorted data, can degrade it to quadratic time. Choosing a random pivot or the median of a few samples makes the bad case extremely unlikely.
Unlike merge sort, quicksort needs almost no extra memory because it sorts within the original array.
Key idea
Quicksort partitions around a pivot and recurses, giving fast in place sorting whose worst case is avoided by smart pivot choice.