Quicksort is a comparison-based sorting algorithm that uses recursion to sort the two parts obtained
by partitioning an array around a selected element. For
an array 
, the partitioning rules are (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 
, so 
).
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."
The left and right subfiles are then sorted by the same algorithm. Quicksort was invented by Hoare (1961, 1962) and has undergone extensive analysis
(Sedgewick 1975, 1977, 1978). Its worst-case cost is 
when the successive partitions are maximally unbalanced.
An already sorted array produces this behavior when the
first or last element is always selected.
Consider the cost model in which processing a nonempty subfile of length 
costs 
units, consisting of one unit to select an element and 
comparisons to partition the remaining
elements. Suppose the keys are distinct and the selected element is chosen uniformly
at random in each subfile. The expectation value 
of the total cost then satisfies the
recurrence equation
 |
(1)
|
for a positive integer 
, with 
(Havil 2003, p. 129). This recurrence
equation can be rewritten as
 |
(2)
|
which has solution
 |
(3)
|
where 
is a harmonic
number, with 
.
For 
, 1, ..., the first few values are
0, 1, 3, 17/3, 53/6, 62/5, 163/10, ... (OEIS A093418
and A096620).
If only the 
comparisons are counted, the corresponding expectation
value is 
(Ekhad and Zeilberger 2019, pp. 3-4).
The cost 
has the asymptotic expansion
 |
(4)
|
where 
is the Euler-Mascheroni
constant. Thus 
,
and in asymptotic notation 
(Havil 2003, p. 130).
