- Developed by British computer scientist Tony Hoare (while he was a visiting student at MSU) in 1959
- Published in 1961
- When implemented well, it
- can be somewhat faster than merge sort
- about two or three times faster than heapsort
- Randomized algorithm (usually implicitly randomized)
Uses divide-and-conquer algorithm.
On each step:
- Randomly select a pivot element
- Partition the other elements in 2 subarrays
- less than pivot
- greater than pivot
- Recursively sort those subarrays
On average: O(n log n) comparisons
Worst case: O(n^2) comparisons
O(1) additional memory (in-place)