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

Sorting Algorithms

Choosing the right sorting algorithm can have a huge impact on application performance. What’s right for one application isn’t necessarily right for a different application. 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 the execution times, but for large data sets, the worst-case bounds become radically different. Beware of data sets that are typically small but may occasionally be much larger — you need to select an algorithm that performs acceptably on the largest data sets your code may encounter.
• Does the data fit in memory? Most sorting algorithms are efficient only when the data they operate on resides in memory. If the data set is too large for memory, you may need to split it into smaller chunks for sorting and then combine those sorted chunks to create the final sorted data set.
• Is the data already mostly sorted? Adding new data to a sorted list can be done efficiently with certain algorithms, but those same algorithms have poor performance on randomly ordered data.
• How much additional memory does the algorithm require? An in-place sorting algorithm sorts the data without using any additional memory, such as by swapping elements in an array. When memory is at a premium, an in-place algorithm may be a better choice than one with otherwise superior efficiency.
• Is relative order preserved? A stable ...