[big oh of n log n] comparisons.
A multikey version of this algorithm employs a three-way radix, and the introsort variant switches to heapsort when a bad case is encountered. In-place implementations of this algorithm requires only O (log n) [big oh of log n] space. Its quadratic worst case, which occurs when a single element is partitioned in each step, is much worse than a similar algorithm whose namesake operation joins two sorted sublists, mergesort, though both perform an average case of O (n log n) [big oh of n log n] comparisons. This algorithm's essential step picks a pivot element and places only smaller elements to the left of it. For 10 points, name this divide-and-conquer sorting algorithm developed by C. A. R. Hoare.
A multikey version of this algorithm employs a three-way radix, and the introsort variant switches to heapsort when a bad case is encountered.
quicksort