**Q:** Suppose we need to
sort all of the customer records for a worldwide investment firm by
name. The data is so large it cannot be fit into memory all at once.
Which sorting algorithm should we use?

**A:** Merge sort. Aside from
running efficiently in *O* (*n*
lg *n*) time, the predictable way that merge sort
divides and merges the data lets us easily manage the data ourselves
to efficiently bring it in and out of secondary storage.

**Q:** Suppose we are
maintaining a list of sorted elements in a user interface. The list is
relatively small and the elements are being entered by a user one at a
time. Which sorting algorithm should we use?

**A:** Insertion sort. The runtime
complexity of insertion sort when inserting a single element into a
list that is already sorted is *O*
(*n*).

**Q:** Suppose we need to
sort 10 million 80-character strings representing DNA information from
a biological study. Which sorting algorithm should we use?

**A:** Radix sort. However,
precisely how radix sort performs in relation to other sorting
algorithms depends on the radix value we choose and our space
constraints. An important consideration in selecting radix sort is
that the elements in the data are a fixed size and can be broken into
integer pieces.

**Q:** Suppose we need to
sort 10,000 C structures containing information about the flight
schedule for an airline. Which sorting algorithm should we use?

**A:** Quicksort. It is the best general-case sorting algorithm and is excellent for medium to large sets of data. ...

Start Free Trial

No credit card required