Chapter 1

Exercise 1.1

We start by proving that $f(N)$ is asymptotically equivalent to $N\lg N$. For sufficiently large $N$, the $\lg N$ term dominates the constant hidden in $O(N)$. Therefore, $\lim_{N \to \infty} |f(N)/(N\lg N)|=|1+O(N)/(N\lg N)|=1$ implying $f(N)=\Theta(N\log N)$.

Exercise 1.2

The book already mentions that there are various strategies to avoid sentinels. For example, on the Algorithms, 4th Edition by RS, KW book’s website, you can find an interesting approach (see the section Creative Problems), that uses a single auxiliary array aux[]. As stated there: "The merge procedure copies the second half of a[] to aux[] in decreasing order and then does the merge back to a[]." This improves performance by eschewing boundary checks on indices. Nonetheless, such a mergesort isn’t stable anymore, which is a key property of this sorting algorithm.

On the same website, you have Merge.java; a standard implementation of the top-down mergesort algorithm without relying on sentinels. As a bonus, it also offers index-based sorting, which avoids moving elements around. Shuffling keys could be expensive if they’re associated with satellite data.

Exercise 1.3

GeeksforGeeks covers 3-way mergesort in great detail.

Below is the driver code to measure execution time. This should replace the original driver code in programs from GeeksforGeeks implementing standard and 3-way mergesort algorithms.

if __name__ == "__main__":
    import random
    import time

    TRIALS = 10
    N = 500_000
    times = []

    for trial in range(1, TRIALS + 1):
        print(f"Trial {trial}/{TRIALS}: generating random list of {N} integers...")
        a = [random.randint(0, 10**9) for _ in range(N)]

        print(f"Trial {trial}: starting...")
        t0 = time.perf_counter()
        # Change this line to call a different target function.
        three_way_merge_sort(a, 0, len(a) - 1)
        t1 = time.perf_counter()
        elapsed = t1 - t0
        times.append(elapsed)
        print(f"Trial {trial} finished in {elapsed:.3f} seconds.")

    avg = sum(times) / len(times)
    print(f"\nRan {len(times)} successful trials. Average: {avg:.3f}s, Min: {min(times):.3f}s, Max: {max(times):.3f}s")

Here are the outputs created on a MacBook Pro 2019 machine:

--- standard mergesort ---
Ran 10 successful trials. Average: 1.980s, Min: 1.895s, Max: 2.055s

--- 3-way mergesort ---
Ran 10 successful trials. Average: 1.931s, Min: 1.887s, Max: 2.014s

3-way mergesort has a lower recursion depth, which may potentially improve performance. It’s a better choice in external sorting scenarios, since it makes fewer passes over datasets typically stored on slow external mediums.

Exercise 1.4

Using the recurrence (1) from the book, we have

$$C_{N+1}-C_N=C_{\lceil (N+1)/2 \rceil}+C_{\lfloor (N+1)/2 \rfloor}+(N+1)-C_{\lceil N/2 \rceil}-C_{\lfloor N/2 \rfloor}-N.$$

Since $\lfloor (N+1)/2 \rfloor=\lceil N/2 \rceil$ and $\lceil (N+1)/2 \rceil=\lfloor N/2 \rfloor +1$ we can simplify the previous equation and get

$$C_{N+1}-C_N=C_{\lfloor N/2 \rfloor +1}-C_{\lfloor N/2 \rfloor}+1.$$

The quantity $\lfloor N/2 \rfloor$ is a positive integer, so we can apply recursively the above expansion by leveraging a useful property of floor and ceiling functions that $\lfloor\lfloor x\rfloor/2 \rfloor=\lfloor x/2 \rfloor$. We can carry out this process until the problem size drops to 1, recalling that $C_1=0$. Thus, we get

$$\begin{align*} C_{N+1}-C_N &= C_{\lfloor N/2 \rfloor +1}-C_{\lfloor N/2 \rfloor}+1 \\ &= C_{\lfloor N/4 \rfloor +1}-C_{\lfloor N/4 \rfloor}+1+1 \\ &\dots \\ &=C_2-C_1+\underbrace{1+1+\dots+1}_{\lfloor \lg N \rfloor \text{ times}} \\ &= 2+\lfloor \lg N \rfloor. \end{align*}$$

Let’s express $C_N$ as a sum of differences, so we have

$$\begin{align*} C_N &= (C_N-C_{N-1})+ (C_{N-1} - C_{N-2}) + \dots+ (C_2-C_1) \\ &=(2+\lfloor\lg (N-1)\rfloor)+(2+\lfloor\lg (N-2)\rfloor)+\dots+(2+\lfloor\lg 1\rfloor) \\ &=\sum_{1 \le k <N} (\lfloor\lg k\rfloor+2). \end{align*}$$

Exercise 1.5 🌟

This exercise showcases an advanced usage of mathematical induction and techniques to manipulate floors and ceilings. Furthermore, it introduces a technique of describing quantities in more detail with additional parameters. For example, a natural number can be interpreted as a binary integer and denoted by $\sum_k2^k$. For an advanced example of this approach, look at the solution of a complex identity.

As mentioned in the book, the theorem for a general $N$ follows from (1) by induction. Let’s use the equation $C_N=N \lceil \lg N \rceil+N-2^{\lceil \lg N \rceil}$ as the inductive hypothesis. The base case $C_1=0$ trivially holds, since $\lg 1=0$. For $N>1$ we have

$$\begin{align*} C_N&=\lceil N/2 \rceil \lceil \lg {\lceil N/2 \rceil} \rceil+\lceil N/2 \rceil-2^{\lceil \lg {\lceil N/2 \rceil} \rceil} \\ &\hspace{1cm} + \lfloor N/2 \rfloor \lceil \lg {\lfloor N/2 \rfloor} \rceil+\lfloor N/2 \rfloor-2^{\lceil \lg {\lfloor N/2 \rfloor} \rceil} && \text{(by the inductive hypothesis)} \\ &\hspace{1cm} +N \\ &= \lceil N/2 \rceil \lceil \lg {\lceil N/2 \rceil} \rceil+\lfloor N/2 \rfloor \lceil \lg {\lfloor N/2 \rfloor} \rceil+2N-2^{\lceil \lg {\lceil N/2 \rceil} \rceil}-2^{\lceil \lg {\lfloor N/2 \rfloor} \rceil} && \text{($N=\lceil N/2 \rceil+\lfloor N/2 \rfloor$)}. \end{align*}$$

If $N$ is even, then $\lceil N/2 \rceil=\lfloor N/2 \rfloor=N/2$, so the last line simplifies to

$$\begin{align*} C_N&=2 \cdot (N/2) \lceil \lg {(N/2)} \rceil+2N- 2\cdot 2^{\lceil \lg {(N/2) } \rceil} \\ &=N \lceil \lg N \rceil-N+2N-2^{\lceil \lg N \rceil} && \text{($\lceil \lg {(N/2)} \rceil=\lceil \lg N-1 \rceil=\lceil \lg N \rceil-1$)} \\ &=N \lceil \lg N \rceil+N-2^{\lceil \lg N \rceil}. && \checkmark \end{align*}$$

If $N$ is odd, then $\lceil N/2 \rceil=(N+1)/2$ and $\lfloor N/2 \rfloor=(N-1)/2$, so we get

$$\begin{align*} C_N&=\frac{N+1}{2} \bigg\lceil \lg \frac{N+1}{2} \bigg\rceil+\frac{N-1}{2} \bigg\lceil \lg \frac{N-1}{2} \bigg\rceil+2N-2^{\big\lceil \lg \frac{N+1}{2} \big\rceil}-2^{\big\lceil \lg \frac{N-1}{2} \big\rceil} \\[0.4cm] &=\frac{N+1}{2} \lceil \lg (N+1) \rceil + \frac{N-1}{2} \lceil \lg (N-1) \rceil-N+2N-2^{\lceil \lg (N+1) \rceil-1}-2^{\lceil \lg (N-1) \rceil-1} \\[0.4cm] &=\frac{N+1}{2} \lceil \lg (N+1) \rceil + \frac{N-1}{2} \lceil \lg (N-1) \rceil+N-2^{\lceil \lg (N +1)\rceil-1}-2^{\lceil \lg (N-1) \rceil-1}. \end{align*}$$

We must figure out how to express $\lceil \lg (N+1) \rceil$ and $\lceil \lg (N-1) \rceil$. We know that $N \in (2^k,2^{k+1})$ for some positive integer $k$. Observe that$\lceil \lg (N+1) \rceil=\lceil \lg N\rceil=k+1$. If $N>2^k+1$ then$\lceil \lg (N-1) \rceil=\lceil \lg N \rceil=k+1$, otherwise $\lceil \lg (N-1) \rceil=\lceil \lg N \rceil-1=k$. Therefore, we must differentiate these two sub-cases.

When $N>2^k+1$ we immediately get

$$\begin{align*} C_N &=\frac{N+1}{2} \lceil \lg N \rceil + \frac{N-1}{2} \lceil \lg N \rceil+N-2^{\lceil \lg N \rceil-1}-2^{\lceil \lg N \rceil-1} \\ &=N \lceil \lg N \rceil +N-2 \cdot 2^{\lceil \lg N \rceil-1} \\ &= N \lceil \lg N \rceil +N-2^{\lceil \lg N \rceil}. \space \space\space\space\checkmark \end{align*}$$

If $N=2^k+1$ observe that $(N-1)/2=(2^k+1-1)/2=2^{k-1}=2^{\lceil \lg N \rceil-2}$. Thus, we have

$$\begin{align*} C_N &=\frac{N+1}{2} \lceil \lg N \rceil + \frac{N-1}{2} \lceil \lg N \rceil-2^{\lceil \lg N \rceil-2}+N-2^{\lceil \lg N \rceil-1}-2^{\lceil \lg N \rceil-2} \\ &=N \lceil \lg N \rceil +N-2^{\lceil \lg N \rceil-1}-2 \cdot 2^{\lceil \lg N \rceil-2} \\ &=N \lceil \lg N \rceil +N-2 \cdot 2^{\lceil \lg N \rceil-1} \\ &=N \lceil \lg N \rceil +N-2^{\lceil \lg N \rceil}. \space \space\space\space\checkmark \end{align*}$$

All in all, we’ve proved that the inductive hypothesis is true for all $N \ge1$.

Exercise 1.6

We use the following three-way merge procedure in Java instead of the original from Exercise 1.3. It uses sentinels, so counting the number of comparisons inside the loop is straightforward.

static void merge(int arr[], int left, int mid1, int mid2, int right) {  
    // Sizes of three subarrays
    int size1 = mid1 - left + 1;
    int size2 = mid2 - mid1;
    int size3 = right - mid2;
        
    // Temporary arrays for three parts
    int[] leftArr = new int[size1 + 1];
    int[] midArr = new int[size2 + 1];
    int[] rightArr = new int[size3 + 1];
        
    // Copy data to temporary arrays
    for (int i = 0; i < size1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int i = 0; i < size2; i++) {
        midArr[i] = arr[mid1 + 1 + i];
    }
    for (int i = 0; i < size3; i++) {
        rightArr[i] = arr[mid2 + 1 + i];
    }
      
    // Add sentinels
    leftArr[size1] = INFTY;
    midArr[size2] = INFTY;
    rightArr[size3] = INFTY;
        
    // Merge three sorted subarrays
    for (int index = left, i = 0, j = 0, k = 0; index <= right; index++) {
        // Find the smallest among the three current elements
        // and place it into the merged array
        if (leftArr[i] <= midArr[j]) {
            if (leftArr[i] <= rightArr[k]) {
                arr[index] = leftArr[i++];	
            } else {
                arr[index] = rightArr[k++];
            }
        } else if (midArr[j] <= rightArr[k]) {
            arr[index] = midArr[j++];
        } else {
            arr[index] = rightArr[k++];
        }
    }
}

Each iteration of the main for loop performs 2 comparisons to decipher the minimum among the 3 candidates. The recurrence is

$$C_N=3C_{N/3 }+2N \space\space \text{for $N \ge 2$ with $C_1=C_0=0$.}$$

If we consider the case when $N$ is a power of 3, and use the same analysis as in the book for the standard mergesort, then we get $C_N=2N\log_3 N$.

Exercise 1.7 🌟

Algorithm science is a methodology for developing machine-independent falsifiable hypotheses. This exercise is about the doubling hypothesis.

According to Exercise 1.1, we know that $t_N=cN \lg N+dN \sim cN \lg N$. We can estimate $t_{2N}$, independent of the machine, as follows:

$$\begin{align*} t_{2N} &\approx 2cN\lg {2N} \\ &=2cN+2cN\lg N \\ &\approx2cN+2t_N \\ &\approx2t_N(1+1/\lg N) && \text{($cN\approx t_N/\lg N$)}. \end{align*}$$

The next Python script shows how well our estimated $t_{2N}$ reflects the actual $t_{2N}$. We can run different experiments by altering the "machine-dependent" constants $c$ and $d$.

from math import log

# Machine dependent constants in the simulation.
c = 3.5
d = 7.1

def t(n):
    return c * n * log(n, 2) + d * n

def estimate_t_2n(t_n, n):
    return 2 * t_n * (1 + 1 / log(n, 2))

for n in [10, 100, 1000, 10000]:
    t_n = t(n)
    est_t_2n = estimate_t_2n(t_n, n)
    act_t_2n = t(2 * n)
    print(f"n: {n:6},\tEstimated: {est_t_2n:10.2f},\tActual: {act_t_2n:10.2f},\tRel. Error: {abs(est_t_2n - act_t_2n) / act_t_2n:.2%}")

The output shows that the relative error drops quickly as $N$ increases.

n:     10,	Estimated:     487.28,	Actual:     444.53,	Rel. Error: 9.62%
n:    100,	Estimated:    6984.43,	Actual:    6770.70,	Rel. Error: 3.16%
n:   1000,	Estimated:   92385.37,	Actual:   90960.49,	Rel. Error: 1.57%
n:  10000,	Estimated: 1152826.43,	Actual: 1142139.87,	Rel. Error: 0.94%

Exercise 1.8

Let’s use the Python implementation of mergesort from GeeksforGeeks and replace the driver code with the following snippet:

import time
from math import log
from random import randint

if __name__ == "__main__":
    for n in (1_000_000, 10_000_000):
        arr = [randint(0, 100) for _ in range(n)]

        start_time = time.time()
        mergeSort(arr, 0, len(arr) - 1)
        end_time = time.time()
        t_n = end_time - start_time

        if n == 1_000_000:
            print(f"Actual 1x time: {t_n:.2f} seconds")
            t10x_estimate = 10 * t_n * (1 + log(10, 2) / log(n, 2))
            print(f"Estimated 10x time: {t10x_estimate:.2f} seconds")
        else:
            print(f"Actual 10x time: {t_n:.2f} seconds")
            print(f"Relative Error: {abs(t_n - t10x_estimate) / t_n:.2%}")

Here’s an output on a MacBook Pro 2019:

Actual 1x time: 4.05 seconds
Estimated 10x time: 47.20 seconds
Actual 10x time: 45.84 seconds
Relative Error: 2.97%

Exercise 1.9

The program Sort2distinct.java implements this algorithm in Java.

The inline comment of the sort method says that it assumes the input has at most 3 distinct values. Without any preprocessing, this should be 2 (see Exercise 1.10).

Exercise 1.10

Perform an initial linear scan to record one set of indices $i$, $j$ and $k$ for those three distinct values. Determine the index of the median and exchange it with an element at the beginning of an array. Finally, run the 3-way partitioning procedure from Exercise 1.9.

As an additional practice, solve the LeetCode problem Sort Colors.

Exercise 1.11 🌟

The number of compares is a reliable estimator of runtime performance of comparison-based sorting algorithms. We can run experiments on different computers to test this hypothesis; the running time of mergesort divided by the number of compares that it uses approaches a constant as the problem size increases.

The following Python program implements this concept. The merge procedure uses sentinels to be aligned with the version from the book.

def merge(a, left, mid, right):
    global c_n # Global counter for number of comparisons

    n1 = mid - left + 1
    n2 = right - mid

    # Create temp arrays
    b = [0] * n1
    c = [0] * n2

    # Copy data to temp arrays b[] and c[]
    for i in range(n1):
        b[i] = a[left + i]
    for j in range(n2):
        c[j] = a[mid + 1 + j]

    # Add sentinels
    b.append(float('inf'))
    c.append(float('inf'))

    # Merge the temp arrays back into a[left..right]
    i = j = 0
    for k in range(left, right + 1):
        c_n += 1 # Simulate profiling by counting comparisons
        if b[i] <= c[j]:
            a[k] = b[i]
            i += 1
        else:
            a[k] = c[j]
            j += 1

def merge_sort(a, left, right):
    if left < right:
        mid = (left + right) // 2
        merge_sort(a, left, mid)
        merge_sort(a, mid + 1, right)
        merge(a, left, mid, right)

if __name__ == "__main__":
    import time
    import random

    print(f"{'n':>10} {'t(n)':>13} {'c(n)':>14} {'t(n)/c(n)':>10}")
    print("-" * 51)
    n = 1
    for _ in range(8):
        n *= 10
        a = [random.randint(0, 10**9) for _ in range(n)]

        start_time = time.time()
        c_n = 0 # Reset comparison counter
        merge_sort(a, 0, len(a) - 1)
        end_time = time.time()
        t_n = (end_time - start_time) * 1_000_000
        print(f"{n:>10} {t_n:>13.2f} {c_n:>14.2f} {t_n / c_n:>10.2f}")

The running time is shown in microseconds. The ratio $t_N/c_N$ stabilizes, as the problem size increases, although there are some fluctuations. Here is the output generated on a MacBook Air 2025 computer:

         n          t(n)           c(n)  t(n)/c(n)
---------------------------------------------------
        10        122.07          34.00       3.59
       100        791.07         672.00       1.18
      1000       5255.94        9976.00       0.53
     10000      37181.85      133616.00       0.28
    100000     233823.30     1668928.00       0.14
   1000000    2852994.92    19951424.00       0.14
  10000000   35313109.64   233222784.00       0.15
 100000000  476664655.92  2665782272.00       0.18

On a MacBook Pro 2019 machine, the constant approached $0.3$.

Exercise 1.12

Let $T_N$ denote the cumulative (total) number of compares used by quicksort on all $N!$ permutations of $N$ elements. The average number of comparisons is $C_N=T_N/N!$, so the base cases are $T_2=6$ and $T_1=T_0=0$. We can derive $T_N$ based upon the simplified recurrence of $C_N$ from the book for $N>2$.

$$\begin{align*} NC_N&=(N+1)C_{N-1}+2N \\[0.2cm] N\left(\frac{T_N}{N!}\right) &= (N+1)\left(\frac{T_{N-1}}{(N-1)!}\right)+2N \\[0.4cm] \frac{T_N}{(N-1)!} &= (N+1)\frac{T_{N-1}}{(N-1)!}+2N \\[0.4cm] &\therefore \boxed{T_N = (N+1)T_{N-1}+2N!}. \end{align*}$$

Exercise 1.13 🌟

The invariant that the subarrays left after partitioning a random permutation are themselves both random permutations is quintessential for analysis and performance. Observe that Program 1.2 only moves the partitioning element (pivot) $v$ to its final position at the end. Leaving the pivot out of the partitioning process is crucial to ensure that the invariant remains true during the whole process.

The proof below is adopted from Sedgewick’s PhD thesis.

Suppose that a permutation of $\{1,2,\dots,N\}$ is being partitioned with all such $N!$ permutations equally likely. Choose a pivot $1 \le v \le N$, so that after partitioning the size of the left subarray becomes $v-1$. Any rearrangement of these $v-1$ elements, out of the possible $(v-1)!$, in the original permutation is mapped to a unique permutation in the left subarray. In other words, we can establish a bijection between these two objects. Since all the original permutations are equally likely, the same is true for permutations in the left subarray. The analogous reasoning applies, independently, for the right subarray. This concludes the proof.

Moving the pivot during the partitioning process, by setting $j:=hi+1$, introduces bias into the subarrays (unless the pivot already happens to be in its final position). The probability of having a permutation where the pivot remains in its initial position is quite low. In our case, the first element from the left larger than the pivot will trigger it to move; it tends to fall near the beginning of the left subarray. Therefore, not all positions are equally likely to contain $v$.

Program 1.2 even becomes incorrect if j is set to hi+1; the line that exchanges a[i] with a[hi] makes no sense anymore, since the pivot, most probably, had already moved somewhere else.

Exercise 1.14

We follow the technique from the book to eliminate summation on the RHS. We have

$$\begin{align*} A_N&=1+\frac{2}{N}\sum_{1\le j \le N}A_{j-1} && \text{(for $N>0$)} \\ NA_N&=N+2\sum_{1\le j \le N}A_{j-1} \\ NA_N-(N-1)A_{N-1}&=1+2A_{N-1} && \text{(for $N>1$, after eliminating summation)} \\ NA_N&=(N+1)A_{N-1}+1 \\ \frac{A_N}{N+1}&=\frac{A_{N-1}}{N}+\frac{1}{(N+1)N} \\ \frac{A_N+1}{N+1}&=\frac{A_{N-1}+1}{N} && \text{$\left(\frac{1}{(N+1)N}=\frac{1}{N}-\frac{1}{N+1}\right)$} \\ \frac{A_N+1}{N+1}&=\frac{A_{N-1}+1}{N}=\dots=\frac{A_1+1}{2} && \text{(iterating)} \\ &\therefore \boxed{A_N=N}. \end{align*}$$

Exercise 1.15 🌟

The derivation augments the technique from the book by introducing an extra dimension. Finding the average number of exchanges used during the first partitioning stage (before the pointers cross) is a harder task than deriving $C_N$ or $A_N$. We have dependencies on both the pivot and arrangement of keys (values to sort).

The proof is adopted from Sedgewick’s PhD thesis.

WLOG assume that the input array is a random permutation of the set $\{1,2,\dots,N\}$. The base cases are $B_1=B_0=0$ and the recurrence is

$$\begin{align*} B_N=&\frac{1}{N}\sum_{1 \le v\le N} \bigg\{\text{average number of exchanges when the pivot is $v$}\bigg \} \\ &+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} && \text{(for $N>1$)}. \end{align*}$$

Let’s analyze the first term of the sum by looking at Program 1.2 from the book. Quicksort is parsimonious regarding exchanges; only those elements are swapped that must be swapped. If the pivot is $v=a[N]$, then only those keys among $a[v],\dots,a[N-1]$ which are smaller than $v$ are exchanged into the right subarray. Furthermore, each element is exchanged at most once during the whole partitioning process. Let $X_v$ be the random variable denoting the number of exchanges used during the first partitioning stage when the pivot is $v$. The probability mass function of $X_v$ is given by

$$\Pr\{X_v=k\}=\frac{\dbinom{N-v}{N-v-k}\dbinom{v-1}{k}}{\dbinom{N-1}{N-v}}=\frac{\dbinom{N-v}{k}\dbinom{v-1}{v-1-k}}{\dbinom{N-1}{v-1}}.$$

The numerator expresses in how many ways we can select $k$ smaller elements from the left subarray and use them to form the right subarray. The denominator is just the total number of possible combinations to form the right subarray. As a side note, the right side of the equation follows from applying the identity $\binom{n}{n}=\binom{n}{n-k}$ and shows symmetry in the problem, i.e., it describes the case when $a[1]$ is chosen as the pivot. At any rate, $k \in [0,v-1]$.

The average number of exchanges is the expectation of $X_v$

$$\begin{align*} \mathbb{E}{[X_v]} &= \sum_{k=0}^{v-1} k\Pr\{X_v=k\} \\[0.5cm] &= \sum_{k=1}^{v-1} {k \cdot \frac{\dbinom{N-v}{k}\dbinom{v-1}{v-1-k}}{\dbinom{N-1}{v-1}} }\\[0.8cm] &= \frac{N-v}{\dbinom{N-1}{v-1}} \sum_{k=1}^{v-1} \binom{N-v-1}{k-1}\binom{v-1}{v-1-k} \\[0.8cm] &= \frac{N-v}{\dbinom{N-1}{v-1}} \sum_{k=0}^{v-2} \binom{N-v-1}{k}\binom{v-1}{v-2-k} \\[0.8cm] &= \frac{N-v}{\dbinom{N-1}{v-1}} \binom{N-2}{v-2} && \text{(Vandermonde convolution)} \\[0.8cm] &= \frac{(N-v)(v-1)}{N-1}. \end{align*}$$

This gives

$$\begin{align*} B_N=&\frac{1}{N}\sum_{1 \le v\le N} \mathbb{E}{[X_v]}+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} \\ =&\frac{1}{N(N-1)}\sum_{1 \le v\le N} (N-v)(v-1)+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} \\ &= \frac{1}{N(N-1)}\binom{N}{3}+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} \\ &= \bold{\frac{N-2}{6}}+\frac{2}{N}\sum_{1\le j \le N}B_{j-1}. \end{align*}$$

If we take into account the official errata, then $B_N \neq \frac{1}{6}C_N-\frac{1}{2}A_N.$ Namely, the equation holds only if we assume that the average partitioning cost in $C_N$ is $N+1$ instead of $N+1-1/N$.

Exercise 1.16 🌟

This exercise demonstrates the significance of algorithm analysis. Having an analytical expression for the average number of small subarrays encountered during sorting can facilitate performance optimization.

Let $B_{Nk}$ denote the number of subarrays of size $k>0$ encountered, on the average, when sorting a random array of size $N$ with quicksort. We have 3 cases:

1. If $N<k$ then we can’t have a subarray of size $k$, so $B_{Nk}=0$.

2. If $N=k$ then $B_{Nk}=1$, since only the initial array is of size $k$.

3. If $N>k$ then the initial call is on a subarray whose size is larger than $k$, hence we don’t count it. We average the counts from the resulting subproblems. The recurrence is

$$B_{Nk}=\frac{2}{N}\sum_{1\le j \le N}B_{(j-1)k}.$$

Fast forwarding the exact same steps as in Exercise 1.14, we get

$$\frac{B_{Nk}}{N+1}=\frac{B_{(N-1)k}}{N}=\dots=\frac{B_{(k+1)k}}{k+2} \space\space\space\space \text{(for $N>k+1$)}.$$

Observe that we can’t iterate further than $B_{(k+1)k}$. Nonetheless, we can calculate it using the main recurrence to get $B_{(k+1)k}=2/(k+1)$; all base cases are zeros except $B_{kk}=1$. Therefore, we have

$$B_{Nk}=\frac{2(N+1)}{(k+1)(k+2)}\space\space\space\space \text{(for $N>k$)}.$$

A simple variation of this problem is the review question Q1.3; the answer is

$B_{Nk}=\cfrac{k(N+1)}{k+2}\qquad \text{(for $N>k$)}.$

Exercise 1.17

Fast forwarding the exact same steps as in the proof of Theorem 1.3, we get

$$\begin{align*} \frac{C_N}{N+1}&=\frac{C_{M+1}}{M+2}+2\sum_{M+3 \le k \le N+1} \frac{1}{k} && \text{(for $N>M+1$)}\\ &=\frac{C_{M+1}}{M+2}+2(H_{N+1}-H_{M+2}). \end{align*}$$

We can calculate $C_{M+1}$ using the main recurrence

$$\begin{align*} C_{M+1} &= (M+1)+1+\frac{2}{M+1}\sum_{1 \le j \le M+1} C_{j-1} \\ &= M+2+\frac{2}{M+1}\sum_{0 \le j \le M} \frac{j(j-1)}{4} && \text{(reindexing and substituting $C_j$)} \\ &= M+2+\frac{1}{2(M+1)}\sum_{1 \le j \le M} j(j-1) \\ &= M+2+\frac{1}{2(M+1)}\left(\frac{M(M+1)(2M+1)}{6}-\frac{M(M+1)}{2}\right) \\ &= M+2+\frac{M(M-1)}{6}. \end{align*}$$

The formula for the average number of compares in quicksort, when using insertion sort to handle small subarrays, is

$$C_N=(N+1)\left(1+\frac{M(M-1)}{6(M+2)}\right)+2(N+1)(H_{N+1}-H_{M+2}) \space\space\space\space \text{(for $N>M$)}.$$

If we take into account the official errata, then the average partitioning cost in $C_N$ is $N+1-1/N$ instead of $N+1$. Thus, the formula changes to

$C_N=(N+1)\left(1-\frac{1}{(M+1)(M+2)}+\frac{M(M-1)}{6(M+2)}\right)+2(N+1)(H_{N+1}-H_{M+2}) \space\space\space\space \text{(for $N>M$)}.$

Exercise 1.18 🌟

Algorithm analysis uses mathematical models to find optimal parameter values, as shown in this example.

After ignoring small terms (those significantly less than $N$) as well as constant multiples of $N$ (they don’t influence the minimization task), we can arrive at the following approximation

$$C_N\approx 2N\ln N +\underset{=f(M)}{\undergroup{\left(\frac{M(M-1)}{6(M+2)}-2\ln {M}\right)}}N.$$

We can use a suitable math tool, like WolframAlpha, to solve the minimization problem as well as plot the graph of $f(M)$. Issue plot m(m-1)/(6(m+2))-2ln(m) for 1<=m<60 to see its shape.

Plot of $f(M)$ that shows a global minimum around 12.

You can find the minimum by saying m(m-1)/(6(m+2))-2ln(m) minimize for m>1 . It reports a global minimum at $M \approx 12.4$.

You may use a different approximation, like using $\lg (M+2)$ instead of $\lg M$ inside $f(M)$, but the outcome would be similar. Also, you may want to try the more accurate expression for $C_N$ (see the remark in the previous exercise).

Exercise 1.19

According to the graph from the previous exercise, the threshold is $M =49$.

Exercise 1.20

Below is the Python script that reports how many keys in a file of $N=10^4$ random positive integers less than $M=10^6$ are likely to be equal to some other keys in the file.

import random
import math
from collections import Counter
from statistics import mean

def count_colliding_keys(n, m):
    # Generate n random positive integers in [1, m-1].
    arr = [random.randrange(1, m) for _ in range(n)]
    freq = Counter(arr)
    # Count all occurrences of values that appear at least twice.
    return sum(cnt for cnt in freq.values() if cnt >= 2)

def simulate(n=10_000, m=1_000_000, trials=1000, seed=None):
    if seed is not None:
        random.seed(seed)
    results = [count_colliding_keys(n, m) for _ in range(trials)]
    mu = round(mean(results))
    analytic = round(n * (1 - (1 - 1/m) ** (n - 1)))
    print(f"n={n}, m={m}, trials={trials}")
    print(f"simulated mean = {mu}")
    print(f"analytic estimate = {analytic}")

simulate(seed=1)

The output shows an excellent alignment between empirical evidence and analytic result:

n=10000, m=1000000, trials=1000
simulated mean = 100
analytic estimate = 99

The analytic formula is the same as for the number of people with a shared birthday; replace the number of days $d$ with $M$.

The program sets the seed of the random number generator. This allows repeatable results even for randomly generated numbers.

Exercise 1.21

Try changing the relative magnitudes of $N$ and $M$ in the previous exercise to see how the number of duplicates increase as $M$ drops, especially when $M \ll N$. The random permutation model assumes that all elements are distinct and all possible $N!$ permutations are equally likely to occur. Nevertheless, even in the presence of many duplicates, Program 1.2 retains good performance. As emphasized in Sedgewick’s paper Quicksort with Equal Keys., the evidence in favor of stopping the scanning pointers on keys equal to the partitioning element in quicksort is overwhelming. This is exactly how partitioning works in Program 1.2.

There are also other schemes to efficiently handle duplicates. The Algorithms, 4th Edition by RS, KW book’s website, has an extensive treatment of quicksort, including variants like fast 3-way and dual-pivot. There’s also background information about entropy optimal sorting, which states the following

Arrays with large numbers of duplicate sort keys arise frequently in applications. In such applications, there’s potential to reduce the time of the sort from linearithmic to linear.

Thus, this is one example where the random permutation model is inaccurate. Of course, the story can go the other way around when partitioning doesn’t account for duplicates. In this case, quicksort may show quadratic runtime.

Exercise 1.22

Essentially, the distribution of keys is "asymptotically" immaterial for mergesort, as it achieves $\Theta(N\lg N)$ runtime in all cases. The sorting numbers specify the worst-case number of comparisons made by mergesort (see also Exercise 1.5). The best case takes about half as many iterations as its worst case; this doesn’t apply to Program 1.1 (see Exercise 1.23). All in all, something like Table 1.1 isn’t useful to get insight into stochastic fluctuations.

On the other hand, Table 1.1 could validate a model, implementation and/or analysis. It could help in revealing machine-dependent constants in a model (see Exercise 1.11) or pinpoint awkward implementation-related issues, perhaps bugs, if the empirical evidence goes against mathematical predictions. Finally, it may assure us that the model for a new variant of mergesort aligns well with empirical data.

Exercise 1.23

The running time of mergesort as implemented in Program 1.1 depends only on the number of elements in the array being sorted, not on their arrangement. Therefore, the standard deviation in the number of compares is zero, since the input size fully determines the cost.