quicksort

Quicksort is a comparison-based sorting algorithm that uses the divide-and-conquer paradigm. It sorts a list by selecting a pivot element and partitioning the remaining elements into those less than the pivot and those greater than or equal to the pivot. The pivot is then placed in its final position, and the process is recursively applied to the subarrays on each side of the pivot. In many implementations, the sort is performed in place, requiring only a small amount of additional storage for indices and the recursion stack.

Two common partition schemes are used to rearrange elements around the pivot. The Hoare partition scheme uses two indices that move toward each other from the ends of the array, swapping elements as needed until they cross. The Lomuto partition scheme typically uses the last element as the pivot and partitions by scanning and swapping elements that are less than the pivot to the front, followed by placing the pivot in its final position. Hoare partitioning generally produces fewer swaps and can be faster in practice, while Lomuto is simpler to implement but may perform more swaps, especially with many duplicates.

The average time complexity of quicksort is O(n log n), making it efficient for large datasets. The worst case is O(n^2), which can occur when the pivot splits the array very unevenly; this risk is mitigated by randomizing the pivot or using more robust pivot selection strategies. Space complexity is typically O(log n) due to recursion depth, with worst-case O(n). Quicksort is not stable in its standard form, meaning equal elements may change order; stable variants exist but are less common in high-performance implementations.

Variations include three-way partitioning to handle duplicates, randomized pivots, and algorithmic hybrids like introsort, which switches to a different sorting method to guarantee worst-case performance. Quicksort remains a foundational algorithm in computer science and is widely used in practice for in-memory sorting.