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)]
```

Worst | Average | Best | |
---|---|---|---|

Time |
\(O(n^2)\) | \(O(n \log n)\) | \(O(n \log n)\) |

Space |
\(O(n)\) |