Quicksort is the fastest known comparison-based sorting algorithm (on average, and for a large number of elements),
requiring 
steps. Quicksort is a recursive algorithm which first partitions an array 
according to several rules (Sedgewick 1978):
1. Some key 
is in its final position in the array (i.e., if it is the 
th smallest, it is in position 
).
2. All the elements to the left of 
are less than or equal to 
. The elements 
, 
,
..., 
are called the "left subfile."
3. All the elements to the right of 
are greater than or equal to 
. The elements 
, ..., 
are called the "right subfile."
Quicksort was invented by Hoare (1961, 1962), has undergone extensive analysis and scrutiny (Sedgewick 1975, 1977, 1978), and is known to be about twice as fast as
the next fastest sorting algorithm. In the worst case,
however, quicksort is a slow 
algorithm (and for quicksort, "worst case" corresponds
to already sorted).
The average time 
for the algorithm to sort a list of 
items arranged in random order is given by the recurrence
equation
 |
(1)
|
with 
(Havil 2003, p. 129). This
recurrence can be rewritten as
 |
(2)
|
which has solution
 |
(3)
|
where 
is a harmonic
number. For 
,
1, ..., the first few values are 0, 1, 3, 17/3, 53/6, 62/5, 163/10, ... (OEIS A093418 and A096620).
This has asymptotic behavior
 |
(4)
|
where 
is the Euler-Mascheroni
constant, which means that 
(Havil 2003, p. 130).
