Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Chapter 8

Sorting

Sorting algorithms are useful for two reasons. The first is to order data for presentation to the user, such as sorting a list of employees alphabetically by first or last name. The second is to simplify and optimize other algorithms, either by sorting the input data prior to applying an algorithm or by sorting the intermediate data an algorithm uses as it runs.

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, you must 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.