next up previous contents index CD CD Algorithms
Next: Searching Up: Combinatorial Problems Previous: Combinatorial Problems




Input description: A set of n items.

Problem description: Arrange the items in increasing order.

Discussion: Sorting is the fundamental algorithmic problem in computer science. Learning the different sorting algorithms is like learning scales for a musician.   Sorting is the first step in solving a host of other algorithm problems, as discussed in Section gif. Indeed, ``when in doubt, sort'' is one of the first rules of algorithm design.

Sorting is also used to illustrate the standard paradigms of algorithm design.   The result is that most programmers are familiar with many different sorting algorithms, which sows confusion as to which should be used for a given application. The following criteria can help you decide:

The best general-purpose sorting algorithm is quicksort (see Section gif), although it requires considerable tuning effort to achieve maximum performance.   Indeed, you are probably better off using a library function instead of doing it yourself. A poorly written quicksort will likely run more slowly than a poorly written heapsort.

If you are determined to implement your own quicksort, use the following heuristics, which make a big difference in practice:

Before you get started, see Bentley's article on building a faster quicksort [Ben92b].

Implementations: Pascal implementations of all the primary sorting algorithms are available from [MS91]. See Section gif for details. Timing comparisons show an optimized version of quicksort to be the winner.  

Bare bones implementations of all basic sorting algorithms, in C and Pascal, appear in [GBY91].   Most notable is the inclusion of implementations of external memory sorting algorithms. Sedgewick includes similar sort routine fragments in C++.   See Section gif for details.

XTango (see Section gif) is an algorithm animation system for UNIX and X-windows, which includes animations of all the basic sorting algorithms, including bubblesort, heapsort, mergesort, quicksort, radix sort, and shellsort. Many of these are quite interesting to watch. Indeed, sorting is the canonical problem for algorithm animation.                

Algorithm 410 [Cha71] and Algorithm 505 [Jan76] of the Collected Algorithms of the ACM are Fortran codes for sorting. The latter is an implementation of Shellsort on linked lists. Both are available from Netlib (see Section gif).      

C language implementations of Shellsort, quicksort, and heapsort appear in [BR95]. The code for these algorithms is printed in the text and available on disk for a modest fee.

A bare bones implementation of heapsort in Fortran from [NW78] can be obtained in Section gif.     A bare bones implementation of heapsort in Mathematica from [Ski90] can be obtained in Section gif.

Notes: Knuth [Knu73b] is the best book that has been written on sorting and indeed is the best book that will ever be written on sorting. It is now almost twenty-five years old, and a revised edition is promised, but it remains fascinating reading. One area that has developed since Knuth is sorting under presortedness measures.   A newer and noteworthy reference on sorting is [GBY91], which includes pointers to algorithms for partially sorted data and includes implementations in C and Pascal for all of the fundamental algorithms.

Expositions on the basic internal sorting algorithms appear in every algorithms text, including [AHU83, Baa88, CLR90, Man89]. Treatments of external sorting are rarer but include [AHU83]. Heapsort was first invented by Williams [Wil64]. Quicksort was invented by Hoare [Hoa62], with careful analysis and implementation by Sedgewick [Sed78].   Von Neumann is credited with having produced the first implementation of mergesort, on the EDVAC in 1945.   See Knuth for a full discussion of the history of sorting, dating back to the days of punched-card tabulating machines.

Sorting has a well-known tex2html_wrap_inline27833 lower bound under the algebraic decision tree model [BO83].   Determining the exact number of comparisons required for sorting n elements, for small values of n, has generated considerable study. See [Aig88, Raw92] for expositions.

This lower-bound does not hold under different models of computation.   Fredman and Willard [FW93] present an tex2html_wrap_inline27835 algorithm for sorting under a model of computation that permits arithmetic operations on keys.   Under a similar model, Thorup [Tho96] developed a priority queue supporting tex2html_wrap_inline27837 operations, implying an tex2html_wrap_inline27839 sorting algorithm.

Related Problems: Dictionaries (see page gif), searching (see page gif), topological sorting (see page gif).      

next up previous contents index CD CD Algorithms
Next: Searching Up: Combinatorial Problems Previous: Combinatorial Problems

Mon Jun 2 23:33:50 EDT 1997