Sorting

By the time they graduate, computer science students are likely to have studied the basic sorting algorithms in their introductory programming class, then in their data structures class, and finally in their algorithms class. Why is sorting worth so much attention? There are several reasons:  

• Sorting is the basic building block around which many other algorithms are built. By understanding sorting, we obtain an amazing amount of power to solve other problems.
• Historically, computers have spent more time sorting than doing anything else. A quarter of all mainframe cycles are spent sorting data [Knu73b]. Although it is unclear whether this remains true on smaller computers, sorting remains the most ubiquitous combinatorial algorithm problem in practice.
• Sorting is the most throughly studied problem in computer science. Literally dozens of different algorithms are known, most of which possess some advantage over all other algorithms in certain situations. To become convinced of this, the reader is encouraged to browse through [Knu73b], with hundreds of pages of interesting sorting algorithms and analysis.
• Most of the interesting ideas used in the design of algorithms appear in the context of sorting, such as divide-and-conquer, data structures, and randomized algorithms.