Thinking Recursively with Java

Chapter 7. Sorting

"I weep for you," the Walrus said:

"I deeply sympathize."

With sobs and tears he sorted out

Those of the largest size.

—Lewis Carroll, Through the Looking-Glass, 1872

In business and commercial applications, programming typically consists of a relatively simple set of operations. For example, report generation is often limited to reading in a file of data and printing it out again in some specific format, possibly including some summary calculations along the way. As long as the operations remain this easy to perform, the fact that these applications also tend to work with vast quantities of data is not an insurmountable concern. Operations such as formatting a report or adding up a column of figures tend to run in linear time. As discussed in Chapter 2, linear time implies that doubling the size of the data merely doubles the amount of time required. For most applications, this increase in running time seems entirely reasonable and well within acceptable bounds.

Unfortunately, not all the operations that characterize business-oriented computing are quite so well behaved. Many applications that work with large amounts of data require the data to be arranged in some sequential ordering. Membership lists and telephone directories, for example, are arranged alphabetically to make each individual entry easier to find. Similarly, bulk mailings are arranged according to ZIP codes to meet the requirements of the U.S. Postal Service. The process of taking an unordered set ...