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

> Why bubble sort is quadratic, explained through inversions; a proof that the divide-and-conquer structure of merge sort achieves n log n; and how the gap between quicksort's average and worst case grows out of the choice of pivot.
> https://rikai.mugen-giken.com/en/computer-science/algorithms/sorting

## 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 id="ex-scale" title="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.
</Example>

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](/en/computer-science/algorithms/complexity-and-big-o) (<Ref to="computer-science/algorithms/complexity-and-big-o#def-big-o" />), and for the underlying arrays, linked lists and heaps on [Fundamental data structures](/en/computer-science/algorithms/data-structures) (<Ref to="computer-science/algorithms/data-structures#def-array" />).

## 2. Preliminaries: the problem and the yardsticks

<Definition id="def-sorting-problem" title="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).
</Definition>

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 id="def-comparison-model" title="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.
</Definition>

All three algorithms treated here are comparison sorts. Within comparison sorting there is a wall at $\Omega(n\log n)$, as stated in <Ref to="thm-comparison-lower-bound" />; counting sort and radix sort evade the wall by stepping outside the model (<Ref to="rem-non-comparison" />).

<Definition id="def-inversion" title="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**.
</Definition>

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 id="def-stability" title="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)$.
</Definition>

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 (<Ref to="computer-science/algorithms/complexity-and-big-o#def-ram" text="the uniform-cost RAM model" />).

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

```python
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 id="thm-bubble" title="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.
</Theorem>

<Proof of="thm-bubble">
**(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 <Ref to="def-inversion" />.

**(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$.
</Proof>

<Example id="ex-bubble-trace" title="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 <Ref to="thm-bubble" />).
</Example>

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 id="prop-adjacent-lower-bound" title="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)$.
</Proposition>

<Proof of="prop-adjacent-lower-bound">
As seen in the proof of part (2) of <Ref to="thm-bubble" />, 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, <Ref to="exr-inversion-expectation" /> shows $\mathbb{E}[\operatorname{inv}] = n(n-1)/4$.
</Proof>

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 id="rem-insertion-sort">
Insertion sort is also $\Theta(n^2)$, but its running time is $\Theta(n + \operatorname{inv}(a))$ (for the count of comparisons see <Ref to="computer-science/algorithms/complexity-and-big-o#ex-insertion-sort" />), 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.
</Remark>

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

<Figure caption="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.">
<Mermaid code={`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"]`} />
</Figure>

```python
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 id="lem-merge" title="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.
</Lemma>

<Proof of="lem-merge">
**(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.
</Proof>

<Theorem id="thm-mergesort" title="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 <Ref to="def-stability" />.
</Theorem>

<Proof of="thm-mergesort">
**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 <Ref to="lem-merge" /> then makes the output of `merge` an increasing sequence of the whole. Stability follows in the same inductive way from part (3) of <Ref to="lem-merge" /> 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 <Ref to="lem-merge" /> 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)$.
</Proof>

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.

<Figure caption="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.">
<svg viewBox="0 0 680 250" width="100%" role="img" aria-label="Diagram showing that each level of the merge sort recursion tree costs cn">
  <g fill="none" stroke="currentColor" stroke-width="1.5">
    <rect x="30" y="16" width="460" height="30" rx="4" />
    <rect x="30" y="76" width="225" height="30" rx="4" />
    <rect x="265" y="76" width="225" height="30" rx="4" />
    <rect x="30" y="136" width="107" height="30" rx="4" />
    <rect x="148" y="136" width="107" height="30" rx="4" />
    <rect x="265" y="136" width="107" height="30" rx="4" />
    <rect x="383" y="136" width="107" height="30" rx="4" />
  </g>
  <g stroke="currentColor" stroke-width="1" opacity="0.55">
    <line x1="260" y1="46" x2="142" y2="76" />
    <line x1="260" y1="46" x2="377" y2="76" />
    <line x1="142" y1="106" x2="83" y2="136" />
    <line x1="142" y1="106" x2="201" y2="136" />
    <line x1="377" y1="106" x2="318" y2="136" />
    <line x1="377" y1="106" x2="436" y2="136" />
  </g>
  <g fill="currentColor" font-size="14" text-anchor="middle">
    <text x="260" y="36">length n</text>
    <text x="142" y="96">n/2</text>
    <text x="377" y="96">n/2</text>
    <text x="83" y="156">n/4</text>
    <text x="201" y="156">n/4</text>
    <text x="318" y="156">n/4</text>
    <text x="436" y="156">n/4</text>
    <text x="260" y="192">… (splitting continues down to length 1) …</text>
  </g>
  <g fill="var(--sl-color-accent)" font-size="14" text-anchor="start">
    <text x="510" y="36">level total cn</text>
    <text x="510" y="96">level total cn</text>
    <text x="510" y="156">level total cn</text>
    <text x="510" y="192">…</text>
  </g>
  <g fill="currentColor" font-size="13" text-anchor="middle">
    <text x="300" y="228">about log₂ n + 1 levels, so the total cost is about cn log₂ n</text>
  </g>
</svg>
</Figure>

<Example id="ex-merge-trace" title="Counting every merge comparison">
We merge-sort the same $a = (8, 3, 5, 1, 9, 2)$ as in <Ref to="ex-bubble-trace" />. 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 <Ref to="thm-mergesort" />. On the same input bubble sort used 15 comparisons and 9 swaps (<Ref to="ex-bubble-trace" />). 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 <Ref to="prop-adjacent-lower-bound" /> is escaped.
</Example>

<Remark id="rem-mergesort-space">
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 <Ref to="def-stability" />. 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](/en/computer-science/algorithms/data-structures), and for the cost of linked-list operations see <Ref to="computer-science/algorithms/data-structures#prop-list" />.
</Remark>

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

```python
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 id="lem-partition" title="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$.
</Lemma>

<Proof of="lem-partition">
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.
</Proof>

By <Ref to="lem-partition" />, 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 id="thm-quicksort-worst" title="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)$.
</Theorem>

<Proof of="thm-quicksort-worst">
**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 <Ref to="lem-partition" /> 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 <Ref to="lem-partition" /> 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.
</Proof>

<Example id="ex-quicksort-sorted" title="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".
</Example>

<Remark id="rem-duplicates">
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.
</Remark>

### 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 id="thm-quicksort-average" title="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)$.
</Theorem>

<Proof of="thm-quicksort-average">
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 <Ref to="thm-quicksort-worst" />, 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 <Ref to="lem-partition" /> 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 <Ref to="lem-partition" /> $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)$.
</Proof>

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 id="rem-pivot-strategies">
Countermeasures against the worst case come down to the choice of pivot.

- **Random choice**: the setting of <Ref to="thm-quicksort-average" />. 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 <Ref to="ex-quicksort-sorted" />. 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.
</Remark>

## 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 id="thm-comparison-lower-bound" title="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)$.
</Theorem>

<Proof of="thm-comparison-lower-bound">
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$.
</Proof>

<Corollary id="cor-mergesort-optimal" title="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)$.
</Corollary>

<Proof of="cor-mergesort-optimal">
The upper bound is <Ref to="thm-mergesort" /> and the lower bound is <Ref to="thm-comparison-lower-bound" />. 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 <Ref to="thm-mergesort" />, while the lower bound $\Omega(n\log n)$ comes from <Ref to="thm-comparison-lower-bound" /> together with the fact that each comparison takes at least constant time; together they give $\Theta(n\log n)$.
</Proof>

<Remark id="rem-non-comparison">
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 <Ref to="def-comparison-model" /> and <Ref to="thm-comparison-lower-bound" /> does not apply to them. A lower bound must always be read together with the statement of the computational model it holds in.
</Remark>

<Aside type="note">
Examples like <Ref to="thm-comparison-lower-bound" />, 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](/computer-science/algorithms/p-vs-np). Upper bounds (exhibiting a fast algorithm) and lower bounds (proving impossibility) are activities of entirely different difficulty.
</Aside>

## 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 (<Ref to="thm-quicksort-worst" />), but recursing only on the shorter side always keeps it within $O(\log n)$ (<Ref to="exr-tail-recursion" />). 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 <Ref to="computer-science/algorithms/searching#thm-binary-cost" /> in [Search algorithms](/computer-science/algorithms/searching)). 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](/computer-science/algorithms/dynamic-programming) (<Ref to="computer-science/algorithms/dynamic-programming#def-dp-formulation" />), which reuses results.

## 8. Exercises

<Exercise id="exr-inversion-expectation" difficulty="Standard">
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 <Ref to="thm-bubble" /> 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.
</Solution>
</Exercise>

<Exercise id="exr-count-inversions" difficulty="Hard">
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.

```python
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 <Ref to="thm-mergesort" /> gives $O(n\log n)$. The closing `assert` agrees with the inversion count $9$ computed by hand in <Ref to="ex-bubble-trace" />. What would take $\Theta(n^2)$ with a double loop is obtained here as a by-product of sorting.
</Solution>
</Exercise>

<Exercise id="exr-tail-recursion" difficulty="Standard">
In the worst case the recursion depth of `quick_sort` reaches $n$ (<Ref to="thm-quicksort-worst" />). 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>
```python
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 <Ref to="ex-quicksort-sorted" />, 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.
</Solution>
</Exercise>

<Exercise id="exr-stability" difficulty="Easy">
(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 <Ref to="thm-mergesort" />.

**(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.
</Solution>
</Exercise>

## 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](https://doi.org/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](https://doi.org/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 (<Ref to="computer-science/algorithms/complexity-and-big-o#thm-master" />) 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 <Ref to="thm-mergesort" />.

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