Programming Interviews Exposed, 4th Edition

9Sorting

Sorting algorithms have several applications. The most obvious is to order data for presentation to the user, such as sorting a list of employees alphabetically by employee ID number or last name. Another important use is as a building block for other algorithms, where having ordered data enables optimizations that wouldn’t otherwise be possible.

You rarely need to code a sorting algorithm. Most languages include at least one sorting algorithm (typically quicksort) in their standard libraries. These built-in algorithms are suitable for general use. In situations in which a general-purpose sorting algorithm doesn’t meet your needs, implementations of specialized sorting algorithms can usually be adapted with minimal effort.

Although you’re unlikely to implement sorting algorithms, it’s important to understand the differences and trade-offs between them. Each algorithm has benefits and drawbacks, and there’s no single best way to sort in all cases. Interviewers like sorting problems because they provide a simple way to address a wide range of issues from algorithmic complexity to memory usage.

SORTING ALGORITHMS

Choosing the right sorting algorithm can have a huge impact on application performance. What’s right in one situation isn’t necessarily right for another. Here are some criteria to consider when selecting a sorting algorithm:

• How much data is to be sorted? For small data sets it doesn’t matter which algorithm you choose because there is little difference in ...