Essential Algorithms: A Practical Approach to Computer Algorithms

CHAPTER 6

Sorting

There are several reasons why sorting algorithms are usually covered in great detail in algorithms books. First, they are interesting and demonstrate several useful techniques, such as recursion, problem subdivision, heaps, and trees.

Second, sorting algorithms are well studied and are some of the few algorithms for which exact run times are known. It can be shown that the fastest possible algorithm that uses comparisons to sort N items must use O(N log N) time. Several sorting algorithms actually achieve that performance, so in some sense they are optimal.

Finally, sorting algorithms are useful. Almost any data is more useful when it is sorted in various ways, so sorting algorithms play an important role in many applications.

This chapter describes several different sorting algorithms. Some, such as insertionsort, selectionsort, and bubblesort, are relatively simple but slow. Others, such as heapsort, quicksort, and mergesort, are more complicated but much faster. Still others, such as countingsort, don't use comparisons to sort items, so they can break the O(N log N) restriction and perform amazingly fast under the right circumstances.

The following sections categorize the algorithms by their run time performance.

NOTE Many programming libraries include sorting tools, and they usually are quite fast. Therefore, in practice, you may want to use those tools to save time writing and debugging the sorting code. It's still important to understand how sorting algorithms ...