11.3 Discussion and Exercises

Sorting is probably the fundamental algorithmic problem in computer science, and has a long history. Knuth [48] attributes the merge-sort algorithm to von Neumann (1945). Quicksort is due to Hoare [39]. The original heap-sort algorithm is due to Williams [76], but the version presented here (in which the heap is constructed bottom-up in $O(\ensuremath{\mathtt{n}})$ time) is due to Floyd [28]. Lower-bounds for comparison-based sorting appear to be folklore. The following table summarizes the performance of these comparison-based algorithms:

	comparisons				in-place
Merge-sort	$\ensuremath{\mathtt{n}}\log \ensuremath{\mathtt{n}}$				worst-case	No
Quicksort	$1.38\ensuremath{\mathtt{n}}\log \ensuremath{\mathtt{n}}$		${}+ O(\ensuremath{\mathtt{n}})$		expected	Yes
Heap-sort	$2\ensuremath{\mathtt{n}}\log\ensuremath{\mathtt{n}}$		${}+ O(\ensuremath{\mathtt{n}})$		worst-case	Yes

Each of these comparison-based algorithms has advantages and disadvantages. Merge-sort does the fewest comparisons and does not rely on randomization. Unfortunately, it uses an auxilliary array during its merge phase. Allocating this array can be expensive and is a potential point of failure if memory is limited. Quicksort is an in-place algorithm and is a close second in terms of the number of comparisons, but is randomized so this running time is not always guaranteed. Heap-sort does the most comparisons, but it is in-place and deterministic.

There is one setting in which merge-sort is a clear-winner; this occurs when sorting a linked-list. In this case, the auxiliary array is not needed; two sorted linked lists are very easily merged into a single sorted linked-list by pointer manipulations (see Exercise 11.2).

The counting-sort and radix-sort algorithms described here are due to Seward [68, Section 2.4.6]. However, variants of radix-sort have been used since the 1920's to sort punch cards using punched card sorting machines. These machines can sort a stack of cards into two piles based on the existence (or not) of a hole in a specific location on the card. Repeating this process for different hole locations gives an implementation of radix-sort.

Finally, we note that counting sort and radix-sort can be used to sort other types of numbers than non-negative integers. Straightforward modifications of counting sort can sort integers, from any interval $\{a,\ldots,b\}$ in $O(\ensuremath{\mathtt{n}}+b-a)$ time. Similarly, radix sort can sort these integers in $O(\ensuremath{\mathtt{n}}(\log_{\ensuremath{\mathtt{n}}}(b-a))$ time. Finally, both these algorithms can also be used to sort floating point numbers in the IEEE 754 floating point format. This is because the IEEE format was designed to allow comparison of two floating point numbers by comparing their values as if they were integers in a signed-magnitude binary representation [2].

Exercise 11..1   Illustrate the execution of merge-sort and heap-sort on an input array containing $1,7,4,6,2,8,3,5$. Give a sample illustration of one possible execution of quicksort on the same array.

Exercise 11..2   Implement a version of the merge-sort algorithm that sorts a DLList without using an auxiliary array. (See Exercise 3.13.)

Exercise 11..3   Some implementations of $\mathtt{quickSort(a,i,n,c)}$ always use $\mathtt{a[i]}$ as a pivot. Given an example of an input array of length $\mathtt{n}$ in which such an implementation would perform $\binom{\ensuremath{\mathtt{n}}}{2}$ comparisons.

Exercise 11..4   Some implementations of $\mathtt{quickSort(a,i,n,c)}$ always use $\mathtt{a[i+n/2]}$ as a pivot. Given an example of an input array of length $\mathtt{n}$ in which such an implementation would perform $\binom{\ensuremath{\mathtt{n}}}{2}$ comparisons.

Exercise 11..5   Show that, for any implementation of $\mathtt{quickSort(a,i,n,c)}$ that chooses a pivot deterministically, without looking at $\ensuremath{\mathtt{a[i]}},\ldots,\ensuremath{\mathtt{a[i+n-1]}}$, there exists an input array of length $\mathtt{n}$ that causes this implementation to perform $\binom{\ensuremath{\mathtt{n}}}{2}$ comparisons.

Exercise 11..6   Design a Comparator, $\mathtt{c}$, that you could pass as an argument to $\mathtt{quickSort(a,i,n,c)}$ and that would cause quicksort to perform $\binom{\ensuremath{\mathtt{n}}}{2}$ comparisons. (Hint: Your comparator does not actually need to look at the values being compared.)

Exercise 11..7   Analyze the expected number of comparisons done by Quicksort a little more carefully than the proof of Theorem 11.3. In particular, show that the expected number of comparisons is $2\ensuremath{\mathtt{n}}H_\ensuremath{\mathtt{n}} -\ensuremath{\mathtt{n}} + H_\ensuremath{\mathtt{n}}$.

Exercise 11..8   Describe an input array that causes heap sort to perform at least $2\ensuremath{\mathtt{n}}\log \ensuremath{\mathtt{n}}-O(\ensuremath{\mathtt{n}})$ comparisons. Justify your answer.

Exercise 11..9   The heap sort implementation described here sorts the elements into reverse sorted order and then reverses the array. This last step could be avoided by defining a new Comparator that negates the results of the input Comparator, $\mathtt{c}$. Explain why this would not be a good optimization. (Hint: Consider how many negations would needed to be done in relation to how long it takes to reverse the array.)

Exercise 11..10   Find another pair of permutations of $1,2,3$ that are not correctly sorted by the comparison-tree in Figure 11.6.

Exercise 11..11   Prove that $\log \ensuremath{\mathtt{n}}! = \ensuremath{\mathtt{n}}\log \ensuremath{\mathtt{n}}-O(\ensuremath{\mathtt{n}})$.

Exercise 11..12   Prove that a binary tree with $k$ leaves has height at least $\log k$.

Exercise 11..13   Prove that, if we pick a random leaf from a binary tree with $k$ leaves, then the expected height of this leaf is at least $\log k$.

Exercise 11..14   The implementation of $\mathtt{radixSort(a,k)}$ given here works when the input array, $\mathtt{a}$ contains only non-negative integers. Extend this implementation so that it also works correctly when $\mathtt{a}$ contains both negative and non-negative integers.