Java Reference
In-Depth Information
1
2
3
4
Figure15.7
Merge insert sort for ten elements. First five pairs of elements are
compared. The five winners are then sorted. This leaves the elements labeled 1-4
to be sorted into the chain made by the remaining six elements.
Call the optimal worst cost for n elements S(n). We know that S(n + 1)
S(n) +dlog(n+ 1)e because we could sort n elements and use binary insert for the
last one. For all n and m, S(n + m) S(n) + S(m) + M(m;n) where M(m;n)
is the best time to merge two sorted lists. For n = 47, it turns out that we can do
better by splitting the list into pieces of size 5 and 42, and then merging. Thus,
merge sort is not quite optimal. But it is extremely good, and nearly optimal for
smallish numbers of elements.
15.8
Further Reading
Much of the material in this topic is also covered in many other textbooks on data
structures and algorithms. The biggest exception is that not many other textbooks
cover lower bounds proofs in any significant detail, as is done in this chapter. Those
that do focus on the same example problems (search and selection) because it tells
such a tight and compelling story regarding related topics, while showing off the
major techniques for lower bounds proofs. Two examples of such textbooks are
“Computer Algorithms” by Baase and Van Gelder [BG00], and “Compared to
What?” by Gregory J.E. Rawlins [Raw92]. “Fundamentals of Algorithmics” by
Brassard and Bratley [BB96] also covers lower bounds proofs.
15.9
Exercises
15.1 Consider the so-called “algorithm for algorithms” in Section 15.1. Is this
really an algorithm? Review the definition of an algorithm from Section 1.4.
Which parts of the definition apply, and which do not? Is the “algorithm for
algorithms” a heuristic for finding a good algorithm? Why or why not?
15.2 Single-elimination tournaments are notorious for their scheduling difficul-
ties. Imagine that you are organizing a tournament for n basketball teams
(you may assume that n = 2
i
for some integer i). We will further simplify
