Sorting Algorithms: Bubble Sort, Merge Sort, Quicksort and the Quadratic Wall

0. Key points

• Bubble sort exchanges only adjacent elements. A single exchange removes exactly one “reversal of order”, so as long as there can be as many as $n(n-1)/2$ reversals, there is no escaping $\Theta(n^2)$. The cause of the slowness is not a crude implementation but the design itself: elements cannot be moved far.
• Merge sort splits the array in half, sorts each half recursively, and then merges the two sorted runs. The number of comparisons is at most $n\lceil \log_2 n\rceil$ and the running time is $\Theta(n \log n)$.
• Quicksort splits the array around a pivot. If the split is balanced the cost is $\Theta(n\log n)$, but if the pivot is taken from a fixed position (the last element, say), then on already sorted input every split degenerates into ”$n-1$ and $0$” and the cost falls to $\Theta(n^2)$.
• If the pivot is chosen uniformly at random, the expected number of comparisons is at most $2n\ln n$. The worst case does not disappear, but it stops being determined by the input and becomes determined by the random choices, which makes it practically unreachable.
• Any sorting method that relies on comparisons alone needs, however cleverly it is arranged, at least $\log_2(n!) \ge n\log_2 n - 1.443\,n$ comparisons in the worst case. Merge sort attains this bound up to a constant factor, and in that sense it has reached the point where “no further speedup is possible”.

1. Motivation: the wall between quadratic time and n log n

Sorting is one of the operations on which computers have spent the most time. In Volume 3 of The Art of Computer Programming, Knuth reports estimates from computer manufacturers of the day according to which more than 25% of running time was spent sorting. Even now, sorting sits at the core of index construction in databases, external joins, extraction of the top $k$ items, and deduplication.

Sorting is also the first subject in which the difference between complexity classes can be felt. Written naively it comes out as $\Theta(n^2)$; written a little more cleverly it comes out as $\Theta(n\log n)$. This gap is not a matter of constant factors.

Example 1.1（Sorting a million records）

Consider a machine performing $10^9$ elementary operations per second, sorting $n = 10^6$ records.

A $\Theta(n^2)$ algorithm makes roughly

$$\frac{n(n-1)}{2} = \frac{10^6 \cdot (10^6 - 1)}{2} \approx 5.0 \times 10^{11}$$

comparisons. Counting a comparison together with its attendant work as a single operation, this is $5.0 \times 10^{11} / 10^9 = 500$ seconds, that is, more than eight minutes.

A $\Theta(n\log n)$ algorithm, since $\log_2 10^6 \approx 19.9$, makes roughly

$$n \log_2 n \approx 10^6 \times 19.9 = 1.99 \times 10^7$$

comparisons, which takes about $0.02$ seconds. The estimate is crude and ignores constant factors, but the ratio is $500 / 0.02 = 25000$. It is the difference between “still running when the lunch break ends” and “finished instantly”. Moreover the ratio is about $(n-1)/(2\log_2 n)$, so multiplying $n$ by ten to get $10^7$ gives $10^7/(2 \times 23.3) \approx 2.1 \times 10^5$: the gap widens by another factor of more than eight.

In this article we explain, in terms of a quantity called the number of inversions, why the naive methods are bound to $\Theta(n^2)$, and then see how divide and conquer breaks that bond. At the end we prove that nothing based on comparisons can beat $\Omega(n\log n)$, and confirm that merge sort is asymptotically optimal. For the complexity notation itself we rely on Complexity and big-O notation (Definition 3.1［Complexity and Big-O Notation］), and for the underlying arrays, linked lists and heaps on Fundamental data structures (Definition 3.1［Fundamental Data Structures］).

2. Preliminaries: the problem and the yardsticks

Definition 2.1（The sorting problem）

Let $(S, \le)$ be a totally ordered set. The input is a sequence $a = (a_0, a_1, \ldots, a_{n-1})$ of length $n$ of elements of $S$. The output is a permutation $\pi$ of $\{0, 1, \ldots, n-1\}$ such that

$$a_{\pi(0)} \le a_{\pi(1)} \le \cdots \le a_{\pi(n-1)}$$

(or, equivalently, the rearranged sequence itself).

Totality matters here. Precisely because for any two elements $x, y$ at least one of $x \le y$ and $y \le x$ holds, every comparison we make returns an answer. For a partial order (where incomparable pairs exist) an output in the above sense may fail to exist at all.

Definition 2.2（The comparison sorting model）

An algorithm is called a comparison sort if the only information it obtains about the input elements is the outcome of comparisons, that is, of queries taking two elements $a_i, a_j$ and asking whether $a_i \le a_j$ holds. Operations such as using the value of an element as an index, or extracting its bits, are not permitted.

All three algorithms treated here are comparison sorts. Within comparison sorting there is a wall at $\Omega(n\log n)$, as stated in Theorem 6.1; counting sort and radix sort evade the wall by stepping outside the model (Remark 6.3).

Definition 2.3（Inversions and the inversion count）

For a sequence $a = (a_0, \ldots, a_{n-1})$, a pair of indices $(i, j)$ with

$$i < j \quad \text{and} \quad a_i > a_j$$

is called an inversion of $a$. The total number of inversions is written $\operatorname{inv}(a)$ and called the inversion count.

The inversion count measures “how disordered the input is”. The condition $\operatorname{inv}(a) = 0$ is equivalent to being sorted in increasing order, and when the elements are distinct the maximum value is $\binom{n}{2} = n(n-1)/2$, attained by the decreasing sequence. This quantity is the key to explaining the slowness of the naive sorts.

Definition 2.4（Stability and being in place）

A sorting algorithm is stable if for any two elements that are equal in the sense of the comparison, their relative order in the input is preserved in the output. It is in place if the working space it uses beyond the input array is $O(1)$ or $O(\log n)$.

Stability matters in practice. When one takes a table sorted by revenue and re-sorts it by department, a stable sort keeps the revenue order within each department. An unstable sort destroys it.

From now on array indices start at $0$, and $\lg n$ denotes $\log_2 n$. Running time is counted taking “one comparison, one assignment” as the unit of time (the uniform-cost RAM model（Definition 2.1）［Complexity and Big-O Notation］).

3. Bubble sort: the price paid for adjacent exchanges

Bubble sort does nothing but repeat one operation: if two adjacent elements are in the wrong order, swap them.

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:      # no swap at all means the array is already sorted
            break
    return a

One pass of the inner loop makes the maximum of the scanned range “bubble up” to the right end. Hence the name.

Theorem 3.1（Correctness and operation count of bubble sort）

For any sequence $a$ of length $n \ge 1$, the algorithm above satisfies the following.

1. It terminates, and its output is $a$ rearranged in increasing order.
2. The number of swaps performed during execution is exactly $\operatorname{inv}(a)$.
3. Without the early exit (the break governed by swapped), the number of comparisons is exactly $n(n-1)/2$. With the early exit the number of comparisons is at most $n(n-1)/2$, with equality on decreasing input.

Proof（Theorem 3.1）

(1) Correctness. We first establish the following invariant for the inner loop.

Immediately after the inner loop finishes the iteration with index $j$, we have $a[j+1] = \max\{a[0], \ldots, a[j+1]\}$ (as values of the array at that moment).

For $j = 0$, the comparison and swap put the larger of $a[0], a[1]$ into $a[1]$, so the claim holds. Assuming it up to $j-1$, at the start of iteration $j$ we have $a[j] = \max\{a[0], \ldots, a[j]\}$. Iteration $j$ compares $a[j]$ with $a[j+1]$ and places the larger into $a[j+1]$, so afterwards $a[j+1] = \max\{a[j], a[j+1]\} = \max\{a[0], \ldots, a[j+1]\}$.

Consequently, immediately after the $i$-th iteration of the outer loop ($i = 0, 1, \ldots$), the position $a[n-1-i]$ holds the maximum of $a[0], \ldots, a[n-1-i]$. We combine this with the outer invariant

immediately after outer iteration $i$, the last $i+1$ entries $a[n-1-i], \ldots, a[n-1]$ are in increasing order and are the $i+1$ largest elements of the whole array

and argue by induction on $i$. The case $i = 0$ is exactly the conclusion above. Assuming it up to $i-1$, iteration $i$ touches only the range $a[0..n-1-i]$ and places its maximum into $a[n-1-i]$. That maximum is “the largest among what remains after removing the top $i$ elements”, hence the $(i+1)$-st largest overall. The claim follows. Once $i = n-2$ is reached, the last $n-1$ positions are correct, and the remaining $a[0]$ is automatically the minimum.

Correctness is preserved when the early exit fires. If some outer iteration performs no swap at all, then at that moment $a[j] \le a[j+1]$ for every $j$ in the undetermined range, and the already-fixed tail consists of larger elements, so the whole array is in increasing order.

(2) Number of swaps. The only movement of elements is the operation “swap an adjacent pair with $a[j] > a[j+1]$”. Consider the effect of this operation on the relative order of pairs of elements of the array. For the pair consisting of the two swapped elements $x = a[j]$ and $y = a[j+1]$ (with $x > y$), before the swap the larger comes first, an inversion; after the swap the smaller comes first, not an inversion. For every other pair of elements, only the two positions $j, j+1$ change places, so the relative order is unaffected. Hence one swap decreases $\operatorname{inv}$ by exactly one.

By (1) the final array is increasing, that is, has inversion count $0$. The inversion count drops by one at each swap and changes at no other time, so the number of swaps equals its initial value $\operatorname{inv}(a)$. Note that equal elements are not swapped, since a[j] > a[j + 1] is false; this is consistent with the strict inequality in Definition 2.3.

(3) Number of comparisons. Without the early exit, in outer iteration $i$ the inner loop compares for $j = 0, \ldots, n-2-i$, that is, $n-1-i$ times. The total is therefore

$$\sum_{i=0}^{n-2} (n-1-i) = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$$

The early exit only removes iterations, so it cannot increase the count. On decreasing input a swap occurs in every iteration up to the last (each iteration still leaves at least one inversion), so the exit never fires and the count is $n(n-1)/2$.

∎

Example 3.2（A complete trace on six elements）

Apply bubble sort to $a = (8, 3, 5, 1, 9, 2)$. Each row records one pass of the inner loop.

Pass	Comparisons	Swaps	Array at the end of the pass
1	5	4	$(3, 5, 1, 8, 2, 9)$
2	4	2	$(3, 1, 5, 2, 8, 9)$
3	3	2	$(1, 3, 2, 5, 8, 9)$
4	2	1	$(1, 2, 3, 5, 8, 9)$
5	1	0	$(1, 2, 3, 5, 8, 9)$ (early exit)

The comparisons total $5+4+3+2+1 = 15 = 6\cdot 5/2$ and the swaps total $4+2+2+1+0 = 9$.

Now count the inversions of $a$ directly. After $8$ the entries smaller than $8$ are $3, 5, 1, 2$, four of them; after $3$ the entries smaller than $3$ are $1, 2$, two of them; after $5$ they are $1, 2$, again two; after $1$ there is nothing smaller, zero; after $9$ there is $2$, one. The total is $4+2+2+0+1 = 9$, in agreement with the number of swaps (part (2) of Theorem 3.1).

So far we have measured “bubble sort is slow”, but we have not yet explained “why it is slow”. The next proposition is the answer.

Proposition 3.3（Lower bound for sorts using only adjacent exchanges）

Consider an algorithm whose only means of moving elements is to swap two adjacent entries of the array. Then the number of swaps needed to sort the input $a$ into increasing order is at least $\operatorname{inv}(a)$. In particular, for inputs of length $n$ with distinct elements, $n(n-1)/2$ swaps are needed in the worst case and, for a uniformly random permutation, $n(n-1)/4$ swaps on average; both are $\Theta(n^2)$.

Proof（Proposition 3.3）

As seen in the proof of part (2) of Theorem 3.1, a single adjacent exchange changes $\operatorname{inv}$ by $\pm 1$ (by $-1$ if it swaps a reversed pair, by $+1$ if it swaps a correctly ordered one). A sorted sequence has $\operatorname{inv} = 0$, so since each step can decrease the count by at most one, going from $\operatorname{inv}(a)$ down to $0$ requires at least $\operatorname{inv}(a)$ swaps.

The worst value is attained on decreasing input, where $\operatorname{inv}(a) = \binom{n}{2} = n(n-1)/2$. As for the average, Exercise 8.1 shows $\mathbb{E}[\operatorname{inv}] = n(n-1)/4$.

∎

The slowness of bubble sort is therefore not something that implementation tricks (early exit, bidirectional passes, and so on) can repair. The toolkit of adjacent exchanges itself demands $\Theta(n^2)$. To go faster we need a mechanism that moves elements far, so that a single operation removes many inversions at once. This is the idea shared by the following sections.

Remark 3.4

Insertion sort is also $\Theta(n^2)$, but its running time is $\Theta(n + \operatorname{inv}(a))$ (for the count of comparisons see Example 2.5［Complexity and Big-O Notation］), so on nearly sorted input ($\operatorname{inv}(a) = O(n)$) it finishes in linear time. Bubble sort does not have this property, because even with the early exit its outer loop runs a number of times proportional to the distance travelled by the element that must move furthest to the left. For small arrays and for nearly sorted arrays, practitioners choose insertion sort.

4. Merge sort: divide and conquer breaks the wall

Divide and conquer is a design principle: split a problem into smaller problems of the same kind, solve them recursively, and combine the solutions. The three stages have names.

• Divide: split the problem into smaller subproblems.
• Conquer: solve the subproblems recursively; if they are small enough, solve them directly.
• Combine: assemble the partial solutions into a solution of the original problem.

Applied to sorting, this reads: “split the array into a front half and a back half, sort each, and merge the two sorted runs.” That is merge sort.

flowchart TB
A["8 3 5 1 9 2"] --> B["8 3 5"]
A --> C["1 9 2"]
B --> D["8"]
B --> E["3 5"]
C --> F["1"]
C --> G["9 2"]
E --> H["3"]
E --> I["5"]
G --> J["9"]
G --> K["2"]

How merge sort divides. Dividing merely halves the array and performs no comparison at all. All the work is done by the merges on the way back from the leaves to the root.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # putting the equality on the left is what makes it stable
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def merge_sort(a):
    if len(a) <= 1:
        return a[:]
    m = len(a) // 2
    return merge(merge_sort(a[:m]), merge_sort(a[m:]))

Lemma 4.1（Correctness and cost of merging）

If left is an increasing sequence of length $p$ and right is an increasing sequence of length $q$, then the merge above satisfies the following.

1. The output is an increasing sequence of length $p+q$ consisting of all elements of left and right.
2. The number of comparisons is at most $p + q - 1$, and the running time is $\Theta(p+q)$.
3. If left and right contain elements that are equal in the sense of the comparison, the element from left is output first.

Proof（Lemma 4.1）

(1) We show that the while loop maintains the following invariant.

result is increasing, and each of its entries is less than or equal to every element of left[i:] and of right[j:]. Moreover result coincides with left[:i] together with right[:j].

Initially $i = j = 0$ and result is empty, so the condition “each entry is at most …” holds vacuously, and left[:0] and right[:0] are both empty. Consider an iteration in which left[i] <= right[j] and left[i] is appended. Since left is increasing, left[i] is the minimum of left[i:]; by the condition it is at most right[j], and since right is increasing it is at most every element of right[j:]. Thus left[i] is the minimum of all remaining elements, so after appending it the invariant “each entry of result is at most every remaining element” still holds and result is still increasing. In the else case (left[i] > right[j]) the element right[j] is likewise the minimum of what remains.

When the loop ends, one of left, right has been consumed entirely. What remains on the other side is increasing and, by the invariant, at least every entry of result, so concatenating it yields an increasing whole. The number of elements and their multiplicities are preserved as well: inside the loop each consumed element is appended to result one at a time, and at the end the unconsumed remainder is concatenated in order, with nothing deleted and nothing duplicated.

(2) Each iteration of the while loop performs one comparison and increases the length of result by one. The loop stops as soon as one of left, right is exhausted, so the number of iterations is at most $p+q-1$ (the last element is always disposed of by concatenation). Together with the concatenations, the number of operations is proportional to $p+q$.

(3) For equal elements left[i] <= right[j] is true, so the element from left is output first.

∎

Theorem 4.2（Correctness and complexity of merge sort）

For any input of length $n \ge 1$, merge_sort terminates and returns the sequence sorted in increasing order. Moreover the number of comparisons $C(n)$ and the running time $T(n)$ satisfy

$$C(n) \le n \lceil \log_2 n \rceil, \qquad T(n) = O(n\log n)$$

The algorithm is also stable in the sense of Definition 2.4.

Proof（Theorem 4.2）

Correctness and termination. By strong induction on the input length $n$. If $n \le 1$ the input is already increasing, and a copy is returned, so the procedure halts. For $n \ge 2$, put $m = \lfloor n/2 \rfloor$; then $1 \le m < n$ and $1 \le n - m < n$, so by the induction hypothesis the two recursive calls halt and return increasing sequences. Part (1) of Lemma 4.1 then makes the output of merge an increasing sequence of the whole. Stability follows in the same inductive way from part (3) of Lemma 4.1 together with the fact that the front half always occupies the left side.

Number of comparisons. Write $h(n) = \lceil \log_2 n \rceil$. Part (2) of Lemma 4.1 gives

$$C(1) = 0, \qquad C(n) \le C(\lceil n/2 \rceil) + C(\lfloor n/2 \rfloor) + (n-1) \quad (n \ge 2)$$

(since merge_sort cuts at $m = \lfloor n/2 \rfloor$, the two parts have lengths $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$).

We first record an auxiliary inequality. Let $n \ge 2$ and $k = h(n)$, so that $k \ge 1$ and $2^{k-1} < n \le 2^k$. Halving and taking the ceiling gives $\lceil n/2 \rceil \le \lceil 2^k / 2 \rceil = 2^{k-1}$, hence $h(\lceil n/2 \rceil) \le k - 1$; and since $h$ is nondecreasing and $\lfloor n/2 \rfloor \le \lceil n/2 \rceil$, also $h(\lfloor n/2 \rfloor) \le k-1$.

Using this we prove $C(n) \le n\,h(n)$ by strong induction on $n$. For $n = 1$ we have $C(1) = 0 = 1 \cdot h(1)$. Let $n \ge 2$ and assume the claim for all smaller values. Putting $a = \lceil n/2 \rceil$ and $b = \lfloor n/2 \rfloor$, so that $a + b = n$ and $a, b < n$, we get

$$\begin{aligned} C(n) &\le a\,h(a) + b\,h(b) + (n-1) \\ &\le a\,(h(n)-1) + b\,(h(n)-1) + (n-1) \\ &= n\,h(n) - n + n - 1 = n\,h(n) - 1 \le n\,h(n) \end{aligned}$$

which is the claim.

Running time. The work outside the merge (slicing the subsequences and managing the recursive calls) is also proportional to the length, so there is a constant $c > 0$ with

$$T(1) \le c, \qquad T(n) \le T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + c\,n$$

We prove $T(n) \le c\,n\,(h(n)+1)$ by the same induction. For $n=1$, $T(1) \le c = c \cdot 1 \cdot (0+1)$. For $n \ge 2$, with the same $a, b$ as above,

$$\begin{aligned} T(n) &\le c\,a\,(h(a)+1) + c\,b\,(h(b)+1) + c\,n \\ &\le c\,a\,h(n) + c\,b\,h(n) + c\,n = c\,n\,(h(n)+1) \end{aligned}$$

(in the second line we used $h(a)+1 \le h(n)$ and $h(b)+1 \le h(n)$). Since $h(n) < \log_2 n + 1$, we obtain $T(n) = O(n \log n)$.

∎

Drawing the content of this proof gives the following picture. At each level of the recursion, the lengths of the subarrays always sum to $n$. The cost of merging is proportional to length, so the total cost at every level is $cn$. There are $\lceil \log_2 n\rceil + 1$ levels, so the whole thing is of order $cn\log n$. Almost everything about why divide-and-conquer complexities take this shape is contained in this single picture.

The recursion tree of merge sort. At each level the subarray lengths sum to n, so the merging cost at each level is cn. With about log₂ n + 1 levels, the total is of order cn log₂ n.

Example 4.3（Counting every merge comparison）

We merge-sort the same $a = (8, 3, 5, 1, 9, 2)$ as in Example 3.2. The division is as in the figure above; we merge upwards from the leaves.

Merge	Inputs	Output	Comparisons
1	$(3)$, $(5)$	$(3,5)$	1
2	$(8)$, $(3,5)$	$(3,5,8)$	2
3	$(9)$, $(2)$	$(2,9)$	1
4	$(1)$, $(2,9)$	$(1,2,9)$	1
5	$(3,5,8)$, $(1,2,9)$	$(1,2,3,5,8,9)$	5

Look closely at merge 2. Here left $=(8)$ and right $=(3,5)$. Since $8 \le 3$ is false we output $3$; since $8 \le 5$ is also false we output $5$; at this point right is exhausted, so the remaining $8$ is concatenated, giving $(3,5,8)$. Two comparisons. In merge 5 we compare $3$ with $1$, $3$ with $2$, $3$ with $9$, $5$ with $9$, and $8$ with $9$, five comparisons, and once left is exhausted the remaining $9$ is concatenated.

The comparisons total $1+2+1+1+5 = 10$, comfortably below the bound $n\lceil \log_2 n\rceil = 6 \times 3 = 18$ of Theorem 4.2. On the same input bubble sort used 15 comparisons and 9 swaps (Example 3.2). Even at $n=6$ the difference already shows.

Note also that in merge 5 the entries $1, 2$, output just before $3$, overtake all three elements of the $(8,3,5)$ side at once. Several inversions are removed by a single operation; this is exactly where the restriction of Proposition 3.3 is escaped.

Remark 4.4

The weak point of merge sort is working space. The implementation above builds a new list at every level of the recursion, so it uses $\Theta(n)$ extra memory and is not in place in the sense of Definition 2.4. Even an implementation that allocates a single scratch array and reuses it still needs $\Theta(n)$. On the other hand, linked lists can be merged by relinking pointers with no auxiliary array at all, which makes merge sort the first choice for external sorting and for list structures. For the trade-offs between data structures see Fundamental data structures, and for the cost of linked-list operations see Proposition 4.2［Fundamental Data Structures］.

5. Quicksort: fast on average, slow at worst

Merge sort was “easy to divide, hard work to combine”. Quicksort reverses this: do the work while dividing, and do nothing while combining. Devised by C. A. R. Hoare in 1959, it repeatedly gathers the elements smaller than a reference value (the pivot) on the left and the larger ones on the right. Once a partition is done the pivot sits in its final position, so sorting the two sides and concatenating them sorts the whole.

We use the Lomuto partition scheme, which is simple to implement.

def partition(a, lo, hi):
    pivot = a[hi]                 # take the last element as the pivot
    i = lo
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]     # move the pivot to the boundary
    return i


def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quick_sort(a, lo, p - 1)
        quick_sort(a, p + 1, hi)
    return a

Lemma 5.1（Correctness of the Lomuto partition）

Let $lo \le hi$ and call partition(a, lo, hi). Writing $p$ for the return value and $v$ for the value of a[hi] before the call, after the call we have

$$lo \le p \le hi, \quad a[p] = v, \quad a[k] \le v \ (lo \le k < p), \quad a[k] > v \ (p < k \le hi)$$

and the multiset of elements of the subarray $a[lo..hi]$ is unchanged. The number of comparisons is exactly $hi - lo$.

Proof（Lemma 5.1）

For the for loop we prove by induction on $j$ that the following invariant holds at the start of iteration $j$:

$$a[k] \le v \ (lo \le k < i), \qquad a[k] > v \ (i \le k < j)$$

For $j = lo$ we have $i = lo$ and both ranges are empty, so the invariant holds. Iteration $j$ splits into two cases. If $a[j] > v$ nothing happens, and the range $i \le k < j+1$ merely acquires the entry $a[j] > v$, so the invariant persists. If $a[j] \le v$ we swap $a[i]$ and $a[j]$. By the invariant the pre-swap $a[i]$ is (when $i < j$) greater than $v$, and after the swap it moves to position $j$, landing at the right end of the “greater than $v$” region. Meanwhile $a[j] \le v$ moves to position $i$, and then $i$ increases by one, so it joins the “at most $v$” region. When $i = j$ the element is swapped with itself and the claim again holds.

At the end of the loop ($j = hi$) we have $a[k] \le v$ for $lo \le k < i$ and $a[k] > v$ for $i \le k < hi$. Finally swapping $a[i]$ with $a[hi] = v$ brings $v$ to position $i$ and moves the value formerly at $a[i]$ (which is greater than $v$) to the last position. Thus with $p = i$ the assertion takes the stated form. That $lo \le i \le hi$ follows because $i$ starts at $lo$ and increases at most $hi - lo$ times. The multiset of elements is unchanged because the only operations are swaps. The comparison a[j] <= pivot is performed exactly once for each $j = lo, \ldots, hi-1$, giving $hi - lo$ comparisons.

∎

By Lemma 5.1, the correctness of quick_sort follows by strong induction on the input length. Since $p$ is a final position, sorting $a[lo..p-1]$ and $a[p+1..hi]$ separately sorts the whole, and both subarrays are strictly shorter than the original. The combining step costs nothing: there is no analogue of the merge.

5.1. Worst-case complexity

Theorem 5.2（Worst-case complexity of deterministic quicksort）

For any input consisting of $n$ distinct elements, the quick_sort above performs at most $n(n-1)/2$ comparisons. Moreover, if the input is already sorted in increasing order, the number of comparisons is exactly $n(n-1)/2$ and the recursion depth reaches $n$. Hence the worst-case complexity is $\Theta(n^2)$.

Proof（Theorem 5.2）

Upper bound. Comparisons occur only in the form a[j] <= pivot, so one of the two compared elements is always the pivot of that call. By Lemma 5.1 the pivot is placed at its final position $p$, and neither of the subsequent recursive calls quick_sort(a, lo, p-1) and quick_sort(a, p+1, hi) contains position $p$. The pivot therefore never appears in any later subarray, so a given pair of elements is compared at most once. The number of pairs is $\binom{n}{2} = n(n-1)/2$, which bounds the number of comparisons.

Equality on sorted input. Calling partition on an increasing subarray of length $m$, the pivot a[hi] is the maximum of that subarray. Hence a[j] <= pivot holds throughout the loop, $i$ increases every time and ends at $i = hi$, and the return value is $p = hi$. All the swaps are with the element itself, so the array remains increasing. The recursion therefore splits into “length $m-1$” and “length $0$”, and by Lemma 5.1 the number of comparisons is $m-1$. Repeating this for $m = n, n-1, \ldots, 2$, the total number of comparisons is

$$(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$$

and the recursion depth is $n$. The work per comparison is constant, so the running time is $\Theta(n^2)$ as well.

∎

Example 5.3（The most unfavourable input）

Apply quick_sort to $a = (1,2,3,4,5)$.

1. partition(a, 0, 4): pivot $=5$. All of $1,2,3,4$ are at most $5$, so $i$ advances $0 \to 4$; finally a[4] is swapped with a[4] and $p=4$. Four comparisons. The left part is $a[0..3]$, the right part is empty.
2. partition(a, 0, 3): pivot $=4$. Likewise $p=3$. Three comparisons.
3. partition(a, 0, 2): pivot $=3$, $p=2$. Two comparisons.
4. partition(a, 0, 1): pivot $=2$, $p=1$. One comparison.

The total is $4+3+2+1 = 10 = 5\cdot 4/2$. For sorted data with $n=10^6$ this means $5\times 10^{11}$ comparisons and, on top of that, a recursion depth of $10^6$, so on most implementations the stack overflows first. This is what lies behind the phenomenon “re-sorting already sorted data froze the program”.

Remark 5.4

Duplicates are another pitfall. Applying the Lomuto partition to an array whose entries are all equal, a[j] <= pivot is always true, so $p = hi$ and we again get the ”$n-1$ and $0$” split, hence $\Theta(n^2)$. The remedy is a three-way partition (of Dutch-national-flag type) that collects the elements equal to the pivot in the middle. Bentley and McIlroy’s “Engineering a Sort Function” is the classic systematic treatment of traps of this kind.

5.2. Average-case complexity

Quicksort remains in use despite its $\Theta(n^2)$ worst case because the average is fast and because that “average” can be guaranteed by randomness. The version that picks the pivot uniformly at random from the subarray is called randomized quicksort (instead of pivot = a[hi], choose an index uniformly between lo and hi, swap it with a[hi], and proceed as before).

Theorem 5.5（Expected number of comparisons of randomized quicksort）

For any input consisting of $n$ distinct elements, the expected number of comparisons $\mathbb{E}[C_n]$ of quicksort with the pivot chosen uniformly at random from the current subarray (independently of previous choices) at every recursive call satisfies

$$\mathbb{E}[C_n] \;=\; \sum_{1 \le i < j \le n} \frac{2}{\,j-i+1\,} \;<\; 2n\,(H_n - 1) \;\le\; 2n \ln n$$

where $H_n = \sum_{k=1}^{n} 1/k$ is the harmonic number. In particular the expected running time is $O(n\log n)$.

Proof（Theorem 5.5）

Write the input in increasing order as $z_1 < z_2 < \cdots < z_n$ and, for $i < j$, put $Z_{ij} = \{z_i, z_{i+1}, \ldots, z_j\}$. Introduce the random variables

$$X_{ij} = \begin{cases} 1 & z_i \text{ and } z_j \text{ are compared during the execution} \\ 0 & \text{otherwise} \end{cases}$$

As seen in the proof of Theorem 5.2, no pair is compared more than once, so the total number of comparisons is $C_n = \sum_{i<j} X_{ij}$. By linearity of expectation, $\mathbb{E}[C_n] = \sum_{i<j} \Pr[X_{ij} = 1]$.

Claim: $z_i$ and $z_j$ are compared if and only if the first element of $Z_{ij}$ to be chosen as a pivot is $z_i$ or $z_j$.

First, as long as all elements of $Z_{ij}$ lie in the same subarray, $z_i$ and $z_j$ have not been compared. Comparisons always involve the pivot, so as long as no pivot has been chosen from $Z_{ij}$, the pair $z_i, z_j$ cannot have been compared. Moreover, during this time a pivot $p$ chosen from outside $Z_{ij}$ does not split $Z_{ij}$. Indeed, if $p \notin Z_{ij}$ then either $p < z_i$ or $p > z_j$ (because $Z_{ij}$ is an interval in the value order); in the first case Lemma 5.1 sends every element of $Z_{ij}$ to the right side, and in the second case all of them to the left side.

So let $p^{*}$ be the first element of $Z_{ij}$ chosen as a pivot. At that moment $Z_{ij}$ still lies in one subarray. If $p^{*} = z_i$ or $p^{*} = z_j$, the pivot is compared with every element of that subarray, so $z_i$ and $z_j$ are compared. If $z_i < p^{*} < z_j$, then by Lemma 5.1 $z_i$ goes to the left and $z_j$ to the right, they never again share a subarray, and they are never compared. The claim is proved.

Computing the probability. When a pivot is chosen uniformly at random from a subarray containing $Z_{ij}$, then conditioned on the chosen element belonging to $Z_{ij}$, each element of $Z_{ij}$ is equally likely. If an element outside $Z_{ij}$ is chosen, then as seen above $Z_{ij}$ is carried over intact into the next subarray and the same argument repeats. Hence “the first element of $Z_{ij}$ to become a pivot” is uniformly distributed on $Z_{ij}$, and the probability that it is $z_i$ or $z_j$ is

$$\Pr[X_{ij} = 1] = \frac{2}{|Z_{ij}|} = \frac{2}{j-i+1}$$

Estimating the sum. Put $d = j - i$ and count.

$$\begin{aligned} \mathbb{E}[C_n] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1} = \sum_{i=1}^{n-1} \sum_{d=1}^{n-i} \frac{2}{d+1} = \sum_{i=1}^{n-1} 2\left(H_{n-i+1} - 1\right) \le 2(n-1)(H_n - 1) \end{aligned}$$

Finally we use $H_n - 1 \le \ln n$. This follows from the inequality $1/k \le \int_{k-1}^{k} dx/x$ for $k \ge 2$ (since $1/x \ge 1/k$ on the interval $[k-1,k]$), which gives

$$H_n - 1 = \sum_{k=2}^{n} \frac{1}{k} \le \int_{1}^{n} \frac{dx}{x} = \ln n$$

Altogether $\mathbb{E}[C_n] < 2n(H_n-1) \le 2n\ln n$. The work outside the comparisons (swaps and index arithmetic) is proportional to the number of comparisons, so the expected running time is $O(n\log n)$.

∎

Since $2n\ln n = 2\ln 2 \cdot n\log_2 n \approx 1.386\, n \log_2 n$, randomized quicksort makes on average about 1.4 times as many comparisons as merge sort’s upper bound. That quicksort is nevertheless often faster in measurements is because it rewrites the array in place without extra memory, giving good cache behaviour, and because its inner loop consists of nothing but “compare, conditionally swap, increment an index”. It is a textbook case of two algorithms with the same $\Theta(n\log n)$ complexity differing in the constant factor.

Remark 5.6

Countermeasures against the worst case come down to the choice of pivot.

• Random choice: the setting of Theorem 5.5. The worst case does not disappear, but its probability depends on the random bits rather than on the input. It also matters in practice that nobody can craft a particular input to slow the program down (short of knowing the random sequence).
• Median of three: take the median of the first, middle and last elements as the pivot. Since a value near the middle is selected on sorted input, this prevents the breakdown of Example 5.3. However, adversarial inputs constructed with knowledge of this rule still force $\Theta(n^2)$.
• Introsort: switch to heapsort once the recursion depth exceeds $2\lfloor \log_2 n \rfloor$. Since heapsort is $O(n\log n)$ in the worst case, the whole thing guarantees $O(n\log n)$ in the worst case while normally running at quicksort speed. This is the scheme used by std::sort in the C++ standard library.

6. The limits of comparison sorting

We now have two $\Theta(n\log n)$ algorithms. Is there a faster comparison sort? The answer is no. Moreover, the proof does not examine individual algorithms: it handles all comparison sorts at once.

The idea is this. A comparison sort cannot look at the input elements directly; it operates using only the answers to comparisons (true or false). The behaviour on $n$ distinct elements can therefore be described by a binary tree (a decision tree) whose internal nodes are queries “is $a_i \le a_j$?”, whose edges are the answers, and whose leaves are the permutations to be output. A single comparison yields one bit of information, so $h$ comparisons distinguish at most $2^h$ outcomes. On the other hand, sorting correctly requires distinguishing all $n!$ rearrangements.

Theorem 6.1（Lower bound for comparison sorting）

For any deterministic comparison sort that correctly sorts $n$ distinct elements, the number of comparisons $h(n)$ required in the worst case satisfies

$$h(n) \ge \log_2 (n!) \ge n \log_2 n - n \log_2 e > n\log_2 n - 1.443\,n$$

In particular $h(n) = \Omega(n\log n)$.

Proof（Theorem 6.1）

Fix the algorithm and consider its decision tree on inputs of $n$ distinct elements. There are $n!$ ways of arranging the input, and each requires a different output permutation. If two distinct arrangements $\sigma \ne \tau$ reached the same leaf of the decision tree, the algorithm would return the same output for both, and at least one of them would be wrong. Hence the decision tree has at least $n!$ leaves.

A binary tree of height $h$ has at most $2^h$ leaves (by induction on $h$: for $h=0$ there is one leaf; a tree of height $h$ has two subtrees at the root, each of height at most $h-1$, so it has at most $2 \cdot 2^{h-1} = 2^h$ leaves). The worst-case number of comparisons equals the height $h$ of the decision tree, so $2^{h} \ge n!$, that is, $h \ge \log_2 (n!)$.

Next we show $n! \ge (n/e)^n$. The power series of the exponential function

$$e^{n} = \sum_{k=0}^{\infty} \frac{n^k}{k!} \ge \frac{n^n}{n!}$$

(the right-hand side keeps only the term $k = n$, all other terms being nonnegative) gives $n! \ge n^n / e^n = (n/e)^n$. Taking $\log_2$ of both sides,

$$\log_2 (n!) \ge n \log_2 \frac{n}{e} = n\log_2 n - n\log_2 e$$

and $\log_2 e = 1.4426\ldots < 1.443$.

∎

Corollary 6.2（Asymptotic optimality of merge sort）

The worst-case number of comparisons of merge sort is at most $n\lceil \log_2 n\rceil$, and its ratio to the lower bound $n\log_2 n - 1.443n$ for any comparison sort tends to $1$ as $n \to \infty$. Thus merge sort is asymptotically optimal among comparison sorts, and its worst-case complexity is $\Theta(n\log n)$.

Proof（Corollary 6.2）

The upper bound is Theorem 4.2 and the lower bound is Theorem 6.1. Assume $n \ge 3$ from now on (then $\log_2 n \ge 1.584 > 1.443$, so the lower bound is positive). Using $\lceil \log_2 n \rceil < \log_2 n + 1$, and the fact that the upper bound is at least the lower bound, the ratio of comparison counts satisfies

$$1 \le \frac{n\lceil \log_2 n\rceil}{\,n\log_2 n - 1.443n\,} < \frac{\log_2 n + 1}{\log_2 n - 1.443} \longrightarrow 1 \quad (n \to \infty)$$

(the limit on the right follows by dividing numerator and denominator by $\log_2 n$, giving $(1 + 1/\log_2 n)/(1 - 1.443/\log_2 n) \to 1$). As for running time, the upper bound $O(n\log n)$ is Theorem 4.2, while the lower bound $\Omega(n\log n)$ comes from Theorem 6.1 together with the fact that each comparison takes at least constant time; together they give $\Theta(n\log n)$.

∎

Remark 6.3

This lower bound comes from the restriction “comparisons only”. Drop the restriction and it breaks. If, for instance, the input is known to consist of integers in the range from $0$ to $K-1$, then counting sort, which counts the occurrences of each value, runs in $\Theta(n + K)$. Radix sort, which stably sorts $d$-digit integers digit by digit starting from the least significant, runs in $\Theta(d(n+K))$. These use element values as array indices, so they lie outside Definition 2.2 and Theorem 6.1 does not apply to them. A lower bound must always be read together with the statement of the computational model it holds in.

Note

Examples like Theorem 6.1, where a lower bound valid for every algorithm can be proved, are in fact rare. It is precisely the strong restriction of the comparison model that lets the information-theoretic argument go through. Showing “this problem requires at least this much” in an unrestricted model of computation is extremely hard, and the emblem of that difficulty is the P vs NP problem. Upper bounds (exhibiting a fast algorithm) and lower bounds (proving impossibility) are activities of entirely different difficulty.

7. Choosing among them

We summarize the three algorithms, adding heapsort for comparison. Here $n$ is the number of elements, and extra memory means working space needed beyond the input array.

Algorithm	Worst-case time	Average time	Extra memory	Stable	Remarks
Bubble sort	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	yes	Almost no practical value; useful as a vehicle for inversions
Insertion sort	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	yes	$\Theta(n + \operatorname{inv})$, hence strong on small or nearly sorted inputs
Merge sort	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n)$	yes	Worst-case guarantee; suited to external sorting and linked lists
Quicksort	$\Theta(n^2)$	$\Theta(n\log n)$	$O(\log n)$	no	Small constant factor, fast in practice; pivot safeguards are essential
Heapsort	$\Theta(n\log n)$	$\Theta(n\log n)$	$O(1)$	no	Worst-case guarantee and in place; somewhat larger constant factor

The extra memory for quicksort is the recursion stack. Written naively the depth can reach $n$ in the worst case (Theorem 5.2), but recursing only on the shorter side always keeps it within $O(\log n)$ (Exercise 8.3). The table assumes that refinement.

Practical decisions run roughly as follows.

• Use the standard library sort. This is the first choice. CPython’s list.sort and Java’s Arrays.sort for object arrays are stable merge sorts of the Timsort family, which detect and exploit the ascending and descending runs already present in the input. C++‘s std::sort is an introsort, and Java’s Arrays.sort for primitive arrays is a quicksort with two pivots. Note that the choice branches on whether stability is required.
• When a worst-case guarantee is needed (when a bound on response time is contractual, or when the input may be chosen adversarially), pick merge sort, heapsort or introsort.
• When memory is tight, pick heapsort or quicksort. There are situations where the $\Theta(n)$ of merge sort cannot be afforded.
• Insertion sort for small subarrays. Fast implementations in practice stop recursing once a subarray falls below a dozen or so elements and switch to insertion sort. Even at $\Theta(n^2)$ the constant factor is small, so for small $n$ it wins.

Finally, “being sorted” is itself a powerful piece of preprocessing. Binary search on a sorted array runs in $O(\log n)$ (see Theorem 3.3［探索アルゴリズム］ in Search algorithms). A design of the form “sort once, then search many times” works precisely because a single $\Theta(n\log n)$ investment makes every subsequent search cost $O(\log n)$. Divide and conquer, moreover, is the technique for subproblems that do not overlap; when subproblems do overlap, the corresponding technique is dynamic programming (Definition 3.1［動的計画法］), which reuses results.

8. Exercises

Exercise 8.1Standard

Show that for a sequence $a$ obtained by arranging $n$ distinct elements uniformly at random, the expected inversion count is

$$\mathbb{E}[\operatorname{inv}(a)] = \frac{n(n-1)}{4}$$

Then use this to determine the average number of swaps performed by bubble sort.

Solution

For a pair of indices $(i,j)$ with $i < j$, let $Y_{ij}$ be the indicator random variable taking the value $1$ when $a_i > a_j$ and $0$ otherwise. By definition $\operatorname{inv}(a) = \sum_{i<j} Y_{ij}$.

We show that $\Pr[Y_{ij}=1] = 1/2$ for a uniformly random permutation. On the set of all permutations, consider the map $\varphi$ that exchanges the values at positions $i$ and $j$. Applying $\varphi$ twice returns to the original ($\varphi \circ \varphi$ is the identity), so $\varphi$ is a bijection and therefore preserves the uniform distribution. And $\varphi$ interchanges the values $0$ and $1$ of $Y_{ij}$. Hence $\Pr[Y_{ij}=1] = \Pr[Y_{ij}=0]$, and since the elements are distinct these two sum to $1$, so both equal $1/2$.

By linearity of expectation (independence is not needed),

$$\mathbb{E}[\operatorname{inv}(a)] = \sum_{i<j} \Pr[Y_{ij}=1] = \binom{n}{2}\cdot\frac{1}{2} = \frac{n(n-1)}{4}$$

By part (2) of Theorem 3.1 the number of swaps performed by bubble sort equals $\operatorname{inv}(a)$, so the average number of swaps is also $n(n-1)/4$, that is, $\Theta(n^2)$. It is merely half of the worst case; the order does not improve.

Exercise 8.2Hard

Construct an algorithm that computes the inversion count $\operatorname{inv}(a)$ of an array in $O(n\log n)$ time by modifying merge sort, and explain why it is correct.

Solution

Split the array into a front half $L$ and a back half $R$. Then the inversions $(i, j)$ fall into three classes.

1. Both $i$ and $j$ lie in the front half.
2. Both $i$ and $j$ lie in the back half.
3. $i$ lies in the front half and $j$ in the back half (a crossing inversion).

Classes 1 and 2 are counted by the recursive calls. Class 3 is counted during the merge. The point is that at merge time $L$ and $R$ are already sorted. When the leading element right[j] of $R$ is output, we have left[i] > right[j]. Since $L$ is sorted, the not-yet-output entries left[i], left[i+1], ..., left[-1] are all at least left[i], hence all greater than right[j]. All of them precede right[j] in the original array, so they create exactly len(left) - i crossing inversions.

Conversely, every crossing inversion $(x, y)$ (with $x \in L$, $y \in R$, $x > y$) is counted exactly once. In the merge the left element is output when left[i] <= right[j], so an $x$ with $x > y$ is output after $y$. That is, at the moment $y$ is output, $x$ is necessarily still unoutput, and it is counted in the len(left) - i at that moment. That is the only time it is counted.

def sort_and_count(a):
    if len(a) <= 1:
        return a[:], 0
    m = len(a) // 2
    left, c_left = sort_and_count(a[:m])
    right, c_right = sort_and_count(a[m:])
    merged, i, j, cross = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            cross += len(left) - i      # every remaining left entry exceeds right[j]
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, c_left + c_right + cross


assert sort_and_count([8, 3, 5, 1, 9, 2]) == ([1, 2, 3, 5, 8, 9], 9)

The complexity obeys the same recurrence $T(n) \le T(\lceil n/2\rceil) + T(\lfloor n/2 \rfloor) + cn$ as merge sort, so the same argument as in the proof of Theorem 4.2 gives $O(n\log n)$. The closing assert agrees with the inversion count $9$ computed by hand in Example 3.2. What would take $\Theta(n^2)$ with a double loop is obtained here as a by-product of sorting.

Exercise 8.3Standard

In the worst case the recursion depth of quick_sort reaches $n$ (Theorem 5.2). Rewriting it so that only the shorter of the two recursive calls is handled by recursion, while the longer one is handled by a loop, bounds the recursion depth by $O(\log n)$ without changing the number of comparisons. Write this implementation and prove the bound on the depth.

Solution

def quick_sort_bounded(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:            # the left side is shorter
            quick_sort_bounded(a, lo, p - 1)
            lo = p + 1                 # handle the right side in the loop
        else:                          # the right side is shorter
            quick_sort_bounded(a, p + 1, hi)
            hi = p - 1                 # handle the left side in the loop
    return a

The collection of subarrays processed is exactly the same as in the original implementation, so neither the number of calls to partition nor the number of comparisons changes.

Now the depth. Partitioning a subarray of length $m$ produces two parts of lengths $m_1, m_2$ with $m_1 + m_2 = m - 1$ (one element, the pivot, is removed). We recurse on the shorter one, whose length is $\min(m_1, m_2) \le (m-1)/2 < m/2$. So each additional level of recursion cuts the subarray length to less than half. Starting from length $n$, the recursion stops once the length is at most $1$; at depth $d$ the length is less than $n/2^d$, which is at most $1$ when $d \ge \log_2 n$. Hence the recursion depth is at most $\lfloor \log_2 n \rfloor$ and the stack usage is $O(\log n)$.

This can be viewed as performing tail call elimination by hand. Even on the sorted input of Example 5.3, the shorter side (of length $0$) is recursed on and the longer side is handled by the loop, so the depth is $1$. The running time is still $\Theta(n^2)$, but at least abnormal termination through stack overflow is avoided.

Exercise 8.4Easy

(a) Explain why it is necessary for the stability of merge sort that the comparison in merge be left[i] <= right[j] and not <.

(b) Show by a concrete three-element example that quicksort with the Lomuto partition is not stable. Take the elements to be pairs consisting of a key and associated data, compared by key alone.

Solution

(a) Consider two elements $x$ (coming from the front half $L$) and $y$ (coming from the back half $R$) with equal keys. In the original array every element of $L$ precedes every element of $R$, so stability requires that $x$ be output before $y$. With the comparison left[i] <= right[j], equal keys make the condition true and the left-hand $x$ comes out first. Had we written left[i] < right[j], equality would send us into the else branch and the right-hand $y$ would come out first, reversing the order. A single character, the side on which the equality sign is placed, decides stability. The order of two elements coming from the same half is preserved by the induction hypothesis, as in the proof of Theorem 4.2.

(b) Write $2_a, 2_b$ for elements with key 2 and $1_c$ for an element with key 1, and take the input

$$a = (2_a,\; 2_b,\; 1_c)$$

Trace partition(a, 0, 2). The pivot is a[2], that is, $1_c$ (key 1), and $i = 0$.

• $j=0$: the key of a[0] is 2 and $2 \le 1$ is false. Nothing happens.
• $j=1$: the key of a[1] is 2 and $2 \le 1$ is false. Nothing happens.

Leaving the loop, swapping a[0] with a[2] makes the array $(1_c,\; 2_b,\; 2_a)$ with return value $p=0$. In the ensuing recursion the right side $(2_b, 2_a)$ is partitioned with pivot $2_a$; since $2 \le 2$ is true, a[1] is swapped with itself, $i$ becomes 2, and finally a[2] is swapped with a[2], leaving the arrangement unchanged. The final output is

$$(1_c,\; 2_b,\; 2_a)$$

The input had the key-2 elements in the order $2_a, 2_b$, but the output has them in the order $2_b, 2_a$. So this implementation is not stable. The cause is that the swap moving the pivot to the boundary at the end of the partition exchanges two elements that are far apart. Being able to move elements far was the source of quicksort’s speed; that same property destroys stability.

References

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — Chapter 2 (insertion sort and merge sort), Chapter 7 (quicksort and the analysis of its expected complexity), Chapter 8 (the comparison-sorting lower bound, counting sort, radix sort).
• D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998 — Chapter 5 (sorting), especially 5.2 (internal sorting). Historical background of each method and precise analyses of the constants.
• C. A. R. Hoare, “Quicksort”, The Computer Journal 5 (1962), 10–16. DOI: 10.1093/comjnl/5.1.10 — the original paper by the inventor.
• J. L. Bentley, M. D. McIlroy, “Engineering a Sort Function”, Software: Practice and Experience 23 (1993), 1249–1265. DOI: 10.1002/spe.4380231105 — implementation design including pivot selection and the handling of duplicate elements.
• D. R. Musser, “Introspective Sorting and Selection Algorithms”, Software: Practice and Experience 27 (1997), 983–993 — the paper proposing introsort (switching between quicksort and heapsort).
• R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 — Chapter 2 (sorting). An exposition centred on implementation and measurement.

Appendix: Solving divide-and-conquer recurrences wholesale

The master theorem. Recurrences such as the $T(n) = 2T(n/2) + \Theta(n)$ that appeared for merge sort show up whenever divide and conquer is used. Instead of solving each one by induction, the following theorem (Theorem 6.1［Complexity and Big-O Notation］) handles them mechanically. Let $a \ge 1$ and $b > 1$ be constants, let $f(n)$ be a nonnegative function, and put

$$T(n) = a\,T(n/b) + f(n)$$

(where $n/b$ may be read as $\lceil n/b \rceil$ or $\lfloor n/b \rfloor$). Setting $\alpha = \log_b a$, the following hold.

• If $f(n) = O(n^{\alpha - \varepsilon})$ for some $\varepsilon > 0$, then $T(n) = \Theta(n^{\alpha})$. (The work at the leaves dominates.)
• If $f(n) = \Theta(n^{\alpha})$, then $T(n) = \Theta(n^{\alpha}\log n)$. (Every level contributes equally.)
• If $f(n) = \Omega(n^{\alpha + \varepsilon})$ for some $\varepsilon > 0$ and moreover $a f(n/b) \le c f(n)$ for some $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$. (The work at the root dominates.)

Application to merge sort. Here $a = 2$, $b = 2$ and $f(n) = \Theta(n)$, so $\alpha = \log_2 2 = 1$ and $f(n) = \Theta(n^{1}) = \Theta(n^{\alpha})$, which is the second case, giving $T(n) = \Theta(n\log n)$. This is the same conclusion as the induction in Theorem 4.2.

The effect of unbalanced splits. The worst case of quicksort is $T(n) = T(n-1) + \Theta(n)$, which is not of the form $n/b$ and so falls outside the master theorem; expanding it directly gives $T(n) = \Theta(n^2)$. On the other hand, a split that is always as lopsided as "$1:9$" — which at first sight looks bad — gives $T(n) = T(n/10) + T(9n/10) + \Theta(n)$, where the recursion tree has depth $\log_{10/9} n = \Theta(\log n)$ and each level costs $O(n)$, so $T(n) = \Theta(n\log n)$ still. An imbalance by a constant ratio only changes the base of the logarithm; it does not break the order. This is why quicksort is fast enough even with merely “decent” splits. Breakdown occurs only when the split fails to maintain a constant ratio, as with “one element and all the rest”.

A caveat. The regularity condition in the third case ($a f(n/b) \le c f(n)$) is not decoration. There are examples, such as oscillating $f$, that fail it and for which the conclusion does not hold. Also, the gaps between the three cases (for instance $f(n) = \Theta(n^{\alpha}\log n)$) are beyond the reach of the master theorem, and require evaluating the recursion tree directly or the more general Akra–Bazzi method. Proofs and precise statements are in Chapter 4 of Cormen et al.