Quicksort selects a ‘pivot’ element from the array then partitions the remaining elements into ‘less than’ and ‘greater than’ sub-arrays. Each of these partitions are then recursively sorted in the same way.
The selection of the pivot element and associated partition methods vary, with quicksort best though of a class of algorithms based around the high-level divide and conquer structure.
QSORT(A): IF A has only one item THEN RETURN A ELSE pivot ← middle item of A (or other pivot scheme) left ← all A < pivot right ← all A > pivot RETURN [QSORT(left) + pivot + QSORT(right)]
|Time||\(O(n^2)\)||\(O(n \log n)\)||\(O(n \log n)\)|