Sorting algorithms - Data Structures and Problem Solving Using Java - page 352

How to write the slightly more complicated O ( N log N ) mergesort
and quicksort algorithms

n

That Ω ( N log N ) comparisons are required for any general-purpose
sorting algorithm

n

why is sorting important?

8.1

Recall from Section 5.6 that searching a sorted array is much easier than
searching an unsorted array. This is especially true for people. That is, finding
a person's name in a phone book is easy, for example, but finding a phone
number without knowing the person's name is virtually impossible. As a
result, any significant amount of computer output is generally arranged in
some sorted order so that it can be interpreted. The following are some more
examples.

Words in a dictionary are sorted (and case distinctions are ignored).

n

Files in a directory are often listed in sorted order.

n

The index of a book is sorted (and case distinctions are ignored).

n

The card catalog in a library is sorted by both author and title.

n

A listing of course offerings at a university is sorted, first by depart-
ment and then by course number.

n

Many banks provide statements that list checks in increasing order by
check number.

n

In a newspaper, the calendar of events in a schedule is generally
sorted by date.

n

Musical compact disks in a record store are generally sorted by
recording artist.

n

In the programs printed for graduation ceremonies, departments are
listed in sorted order and then students in those departments are listed
in sorted order.

n

Not surprisingly, much of the work in computing involves sorting. How-
ever, sorting also has indirect uses. For instance, suppose that we want to
decide whether an array has any duplicates. Figure 8.1 shows a simple method
that requires quadratic worst-case time. Sorting provides an alternative algo-
rithm. That is, if we sort a copy of the array, then any duplicates will be adja-
cent to each other and can be detected in a single linear-time scan of the array.
The cost of this algorithm is dominated by the time to sort, so if we can sort in

An initial sort of the
data can signifi-
cantly enhance the
performance of an
algorithm.