8. Sorting in Linear Time

Exercises

8.1-1

The smallest possible depth of a leaf in a decision tree for a comparison sort is $n-1$, where $n$ is the number of elements to sort. This is equivalent to the best-case number of comparisons needed to sort $n$ elements. For example, insertion sort will make this number of comparison when given an already sorted array on input.

8.1-2

Available in the latest revision of the IM.

8.1-3

Available in the latest revision of the IM.

8.1-4

Available in the latest revision of the IM.

8.2-1

// The array A and the auxiliary array C after line 5.
A[1:11]=[6,0,2,0,1,3,4,6,1,3,2]
C[0:6]=[2,2,2,2,1,0,2]

// The array C after line 8.
C[0:6]=[2,4,6,8,9,9,11]

// The output array B and the auxiliary array C after one, two, and 
// three iterations of the loop in lines 11–13, respectively. 
// Only the non-X elements of array B have been filled in.
B[1:11]=[X,X,X,X,X,2,X,X,X,X,X]
C[0:6]=[2,4,5,8,9,9,11]

B[1:11]=[X,X,X,X,X,2,X,3,X,X,X]
C[0:6]=[2,4,5,7,9,9,11]

B[1:11]=[X,X,X,1,X,2,X,3,X,X,X]
C[0:6]=[2,3,5,7,9,9,11]

// The final sorted output array B.
B[1:11]=[0,0,1,1,2,2,3,3,4,6,6]

8.2-2

Consider the case where positions $i < j$ each contain the same value $v$. Focusing on lines 11 through 13 of Counting-Sort, which fill the output array, we observe that the loop will process $A[j]$ prior to $A[i]$. In this situation, $A[j]$ is placed into position $p = C[v]$ of $B$. Following this placement, line 13 decrements $C[v]$, ensuring that when the loop later processes $A[i]$, the value of $C[v]$ is less than $p$. Consequently, $A[i]$ is inserted into an earlier location in the output array, thereby demonstrating the stability of the algorithm.

8.2-3

Available in the latest revision of the IM.

The pseudocode in the IM needlessly wastes memory by introducing a new array $L$. The array $C$ can be updated in-place such that $C[i]$ contains the index of the first element of $A$ with value $i$. The following snippet does the job: p = 1 for i = 1 to k q = C[i] C[i] = p + C[i-1] p = q C[0] = 1

8.2-4

Available in the latest revision of the IM.

8.2-5

Available in the latest revision of the IM.

8.2-6

Available in the latest revision of the IM.

8.2-7

Available in the latest revision of the IM.

8.3-1

COW   SEA   TAB   BAR
DOG   TEA   BAR   BIG
SEA   MOB   EAR   BOX
RUG   TAB   TAR   COW
ROW   DOG   SEA   DIG
MOB   RUG   TEA   DOG
BOX   DIG   DIG   EAR
TAB   BIG   BIG   FOX
BAR   BAR   MOB   MOB
EAR   EAR   DOG   NOW
TAR   TAR   COW   ROW
DIG   COW   ROW   RUG
BIG   ROW   NOW   SEA
TEA   NOW   BOX   TAB
NOW   BOX   FOX   TAR
FOX   FOX   RUG   TEA

8.3-2

Available in the latest revision of the IM.

8.3-3

Available in the latest revision of the IM.

8.3-4 🌟

This exercise illustrates the importance of examining the hidden constant factors underlying Big-O notation. Although reducing the number of passes does not alter the asymptotic complexity, it decreases the constant factor and can therefore produce substantial practical performance improvements.

Available in the latest revision of the IM.

8.3-5

Available in the latest revision of the IM.

★ 8.3-6

Each sorting pass corresponds to feeding a pile of cards into the machine to be sorted into 10 bins based on the current digit. The total number of sorting passes in the worst-case (every possible combination of digits exists) is $S(d)=\sum_{i=0}^{d-1} 10^i=\frac{10^d-1}{9}$.

The phrase "keep track of" is slightly ambiguous, so we cover two possible interpretations:

• The total number of intermediate piles produced during the whole process is commensurate with the number of sorting passes. The cards in 9 of the 10 bins must be put aside to sort each of the bins, except when sorting on the least significant digit position. We have $P(d)=9(S(d)-10^{d-1})=10^{d-1}-1$.

• If we are interested in to estimate the space needed for storing those intermediate piles at any given moment, then we have $P(d)=9(d-1)+1$, where +1 designates the pile being placed into a machine for sorting.

8.4-1

Available in the latest revision of the IM.

8.4-2

Available in the latest revision of the IM.

8.4-3

Available in the latest revision of the IM.

8.4-4

The idea is to split buckets into 2 layers. This works, since $n>10$ implies that $y_i/n<\lfloor10x_i\rfloor/10$. Below is the implementation of the modified bucket sort in Python 3. For the sake of simplicity, we skip corner cases associated with rounding errors.

def modified_bucket_sort(a):
    n = len(a)
    
    # Step 1: Create 10 main buckets.
    b = [[] for _ in range(10)]
    for num in a:
        b[int(num * 10)].append(num)

    # Step 2: Process each main bucket.
    sorted_a = []
    for i in range(10):
        # Create n sub-buckets for the current main bucket.
        c = [[] for _ in range(n)]
        for num in b[i]:
            y = n * (num - i / 10)
            c[int(y * n)].append(num)
        # Concatenate all sorted sub-buckets of the current main bucket.
        for j in range(n):
            # Each sub-bucket is expected to have O(1) elements.
            sorted_a.extend(sorted(c[j]))
    return sorted_a

★ 8.4-5

Available in the latest revision of the IM.

★ 8.4-6 🌟

Introduces the probability integral transform.

The algorithm has two major steps based on bucket sort.

1

Initialize

Create $n$ buckets. For $i=1,2,\dots,n$ place $X_i$ into bucket $\lfloor P(X_i)n\rfloor$. This stage requires $O(n)$ time. The fact that $Y_i=P(X_i)$ has a uniform distribution over $[0,1)$, due to the probability integral transform, ensures that each bucket's expected size is $O(1)$.

2

Sort and Concatenate

Because $P(x)$ is a valid probability distribution function, it is monotonically increasing. This means that $X_A < X_B \implies P(X_A) \le P(X_B)$. Therefore, grouping the elements by their transformed values $P(X_i)$ guarantees they are also ordered by their original values $X_i$. Sort the elements within each individual bucket. Finally, concatenate the sorted buckets to produce the final sorted array.

Problems

8-1 Probabilistic lower bounds on comparison sorting

Available in the latest revision of the IM.

8-2 Sorting in place in linear time

Available in the latest revision of the IM.

8-3 Sorting variable-length items

Available in the latest revision of the IM.

Wikipedia examines this problem in some detail in its article about radix sort.

8-4 Water jugs

Available in the latest revision of the IM.

8-5 Average sorting

a.

It is equivalent to be sorted in usual way.

b.

1,3,2,4,6,5,7,9,8,10

c.

We first prove the "only if" direction. For all $i=1,2,\dots,n-k$ we have

$$\begin{align*} \frac{\sum_{j=i}^{i+k-1}A[j]}{k} &\le \frac{\sum_{j=i+1}^{i+k}A[j]}{k} \\ \sum_{j=i}^{i+k-1}A[j] &\le \sum_{j=i+1}^{i+k}A[j] && \text{(eliminating $k$ from both sides)} \\ A[i] &\le A[i+k] && \text{(cancelling equal terms on both sides)}. \end{align*}$$

The "if" direction is simply an inverse of the previous steps.

d.

By part (c) we can split the input numbers into k independent chains and sort them separately. Each chain has $n/k$ elements. For example, the first chain begins as $A[1],A[1+k],A[1+2k],...$ The time to sort a chain is $O((n/k) \lg (n/k))$ using heap sort or merge sort. The total time for all $k$ chains is $O(n\lg(n/k))$.

e.

Following the hint from the book, we apply the $k$-way merge algorithm, since a $k$-sorted array can be regarded as having $k$ sorted lists, that need to be combined (merged) into one sorted output.

f.

Let $T(n)$ be the time it takes to $k$-sort an array of $n$ elements. To 1-sort an array of $n$ elements, we can first $k$-sort it and then employ the algorithm from part (e). Since we know the lower bound on comparison sorts, this gives

$$T(n) + O(n \lg k)=T(n)+O(n) = \Omega(n \lg n).$$

Recall that $k>1$ is a constant. Therefore, we must have $T(n)=\Omega(n \lg n)$.

8-6 Lower bound on merging sorted lists

a.

This equals the number of ways to pick $n$ items out of $2n$ items. Observe that once we select the first batch of $n$ numbers the second one is automatically determined. We have (see Exercise C.1-13)

$$\binom{2n}{n}=\cfrac {2^{2n}}{\sqrt{\pi n}}(1+O'(1/n)).$$

b.

The following inequalities must hold, where $l$ is the number of leaves in a decision tree of height $h$.

$$\cfrac {2^{2n}}{\sqrt{\pi n}}(1+O'(1/n)) \le l \le 2^h.$$

Taking logarithms on both sides, we get

$$\begin{align*} h &\ge \lg \left({\cfrac {2^{2n}}{\sqrt{\pi n}}(1+O'(1/n))}\right) \\ &= \lg 2^{2n} - \lg \sqrt{\pi n} + \lg (1+O'(1/n)) \\ &= 2n-o(n). \end{align*}$$

c.

Suppose $a_i \neq b_j$. We know that the inequalities below are all satisfied, since $a_i$ and $b_j$ are from different sorted lists and they are consecutive in the sorted order.

$$a_{i-1} < a_i ,b_j < a_{i+1} \\ b_{j-1} < a_i ,b_j < b_{j+1}$$

We could exchange $a_i$ and $b_j$ without violating any of the constraints above. No matter how many other comparisons are made, none of them can add any new information about the relative order of $a_i$ and $b_j$. Therefore, $a_i$ and $b_j$ must be compared.

d.

The worst-case number of comparisons happens when elements are taken in alternating manner from sublists during the merge operation, hence, consecutive elements in the sorted order are from different lists. By part (c) they must be compared and we have $2n-1$ such pairs.

8-7 The 0-1 sorting lemma and columnsort

Available in the latest revision of the IM.