Skip to content

Week 6 - Comparison Sort and Linear Sort

Assignment - Due 11/03/2018

Credit: source code of questions are from walkccc.


What is the smallest possible depth of a leaf in a decision tree for a comparison sort?

The best case time happens when the array is already sorted, and it needs n - 1 comparisons to show, so the smallest possible depth also n - 1.


Obtain asymptotically tight bounds on \lg(n!) without using Stirling's approximation. Instead, evaluate the summation \sum_{k = 1}^n \lg k using techniques from Section A.2.


Show that there is no comparison sort whose running time is linear for at least half of the n! inputs of length n. What about a fraction of 1 / n of the inputs of length n? What about a fraction 1 / 2^n?


Suppose that you are given a sequence of n elements to sort. The input sequence consists of n / k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n / k subsequences. Show an \Omega(n\lg k) lower bound on the number of comparisons needed to solve this variant of the sorting problem. (\textit{Hint:} It is not rigorous to simply combine the lower bounds for the individual subsequences.)


Using Figure 8.2 as a model, illustrate the operation of \text{COUNTING-SORT} on the array A = \langle 6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2 \rangle.


Prove that \text{COUNTING-SORT} is stable.


Suppose that we were to rewrite the for loop header in line 10 of the \text{COUNTING-SORT} as

10  for j = 1 to A.length

Show that the algorithm still works properly. Is the modified algorithm stable?


Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a..b] in O(1) time. Your algorithm should use \Theta(n + k) preprocessing time.


Using Figure 8.3 as a model, illustrate the operation of \text{RADIX-SORT} on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.


Show how to sort n integers in the range 0 to n^3 - 1 in O(n) time.