The Algorithm Design Manual Second Edition

Chapter Notes

The most interesting sorting algorithms that have not been discussed in this section

include shellsort, which is a substantially more efficient version of insertion sort,

and radix sort, an efficient algorithm for sorting strings. You can learn more about

these and every other sorting algorithm by browsing through Knuth

[Knu98

], with

hundreds of pages of interesting material on sorting. This includes external sorting,

the subject of this chapter’s legal war story.

As implemented here, mergesort copies the merged elements into an auxiliary

buffer to avoid overwriting the original elements to be sorted. Through clever but

complicated buffer manipulation, mergesort can be implemented in an array with-

out using much extra storage. Kronrod’s algorithm for in-place merging is presented

in

[Knu98]

.

Randomized algorithms are discussed in greater detail in the books by Mot-

wani and Raghavan

[MR95

] and Mitzenmacher and Upfal

[MU05

]. The problem of

b

log  n

b

log  a

n

=

width = a

---

4 . 1 1

E X E R C I S E S

139

nut and bolt sorting was introduced by

[Raw92

]. A complicated but deterministic

O(n log n) algorithm is due to Komlos, Ma, and Szemeredi

[KMS96

].

Several other algorithms texts provide more substantive coverage of divide-

and-conquer algorithms, including

[CLRS01

,

KT06

,

Man89

]. See

[CLRS01

] for an

excellent overview of the master theorem.