The Algorithm Design Manual Second Edition

Implementations

: The best freely available sort program is presumably GNU

sort, part of the GNU core utilities library. See http://www.gnu.org/software/

coreutils/. Be aware that there are also commercial vendors of high-performance

external sorting programs. These include Cosort (www.cosort.com), Syncsort

(www.syncsort.com) and Ordinal Technology (www.ordinal.com).

Modern programming languages provide libraries offering complete and effi-

cient container implementations. Thus, you should never need to implement your

own sort routine. The C standard library contains qsort, a generic implementa-

tion of (presumably) quicksort. The C++ Standard Template Library (STL) pro-

vides both sort and stable sort methods. It is available with documentation

at http://www.sgi.com/tech/stl/. See Josuttis [

Jos99]

, Meyers [

Mey01]

and Musser

[

MDS01]

for more detailed guides to using STL and the C++ standard library.

Java Collections (JC), a small library of data structures, is included in the

java.util package of Java standard edition (http://java.sun.com/javase/). In par-

ticular, SortedMap and SortedSet classes are provided.

For a C++ implementation of an cache-oblivious algorithm (funnelsort), check

out http://kristoffer.vinther.name/projects/funnelsort/. Benchmarks attest to its

excellent performance.

There are a variety of websites that provide applets/animations of all the ba-

sic sorting algorithms, including bubblesort, heapsort, mergesort, quicksort, radix

sort, and shellsort. Many of these are quite interesting to watch. Indeed, sort-

ing is the canonical problem for algorithm animation. Representative examples

include Harrison (http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html)

and Bentley [

Ben99]

(http://www.cs.bell-labs.com/cm/cs/pearls/sortanim.html).

Notes

:

Knuth

[Knu98]

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 over thirty years old,

but remains fascinating reading. One area that has developed since Knuth is sorting

under presortedness measures, surveyed in [

ECW92]

. A 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.

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 punch-card

tabulating machines.

The primary competitive forum for high-performance sorting is an annual competition

initiated by the late Jim Gray. See http://research.microsoft.com/barc/SortBenchmark/

for current and previous results, which are are either inspiring or depressing depending

---

440

1 4 .

C O M B I N A T O R I A L P R O B L E M S

upon how you look at it. The magnitude of progress is inspiring (the million-record in-

stances of the original benchmarks are now too small to bother with) but it is depressing

(to me) the extent that systems/memory management issues thoroughly trump the com-

binatorial/algorithmic aspects of sorting.

Modern attempts to engineer high-performance sort programs include work on both

cache-conscious

[LL99]

and cache-oblivious

[BFV07]

sorting.

Sorting has a well-known Ω(n lg n) 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

and Peczarski

[Pec04, Pec07]

for the latest results.

This lower-bound does not hold under different models of computation. Fredman and

Willard

[FW93]

present an O(n

√

lg n) algorithm for sorting under a model of computa-

tion that permits arithmetic operations on keys. See Andersson

[And05]

for a survey of

algorithms for fast sorting on such nonstandard models of computation.