> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-ii-sorting-and-order-statistics/8.-sorting-in-linear-time.md). # 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.** {% hint style="warning" %} 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` {% endhint %} ### 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 🌟 {% hint style="success" %} 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. {% endhint %} **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. ```python 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 🌟 {% hint style="success" %} Introduces the [probability integral transform](https://en.wikipedia.org/wiki/Probability_integral_transform). {% endhint %} The algorithm has two major steps based on bucket sort. {% stepper %} {% step %} ### 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)$$. {% endstep %} {% step %} ### 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. {% endstep %} {% endstepper %} ## 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.** {% hint style="info" %} Wikipedia examines this problem in some detail in its article about [radix sort](https://en.wikipedia.org/wiki/Radix_sort). {% endhint %} ### 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](https://evarga.gitbook.io/sh-intro-to-algs/part-ii-sorting-and-order-statistics/pages/QwHFLVleY7QejI9V4gc3#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.** --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://evarga.gitbook.io/sh-intro-to-algs/part-ii-sorting-and-order-statistics/8.-sorting-in-linear-time.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.