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).