Donald E. Knuth - Sorting and Searching

ePUB is an open, industry-standard format for eBooks. However, support of ePUB and its many features varies across reading devices and applications. Use your device or app settings to customize the presentation to your liking. Settings that you can customize often include font, font size, single or double column, landscape or portrait mode, and figures that you can click or tap to enlarge. For additional information about the settings and features on your reading device or app, visit the device manufacturers Web site.

Many titles include programming code or configuration examples. To optimize the presentation of these elements, view the eBook in single-column, landscape mode and adjust the font size to the smallest setting. In addition to presenting code and configurations in the reflowable text format, we have included images of the code that mimic the presentation found in the print book; therefore, where the reflowable format may compromise the presentation of the code listing, you will see a Click here to view code image link. Click the link to view the print-fidelity code image. To return to the previous page viewed, click the Back button on your device or app.

In this eBook, the limitations of the ePUB format have caused us to render some equations as text and others as images, depending on the complexity of the equation. This can result in an odd juxtaposition in cases where the same variables appear as part of both a text presentation and an image presentation. However, the authors intent is clear and in both cases the equations are legible.

Volume 3 / Sorting and Searching

SECOND EDITION

DONALD E. KNUTHStanford University

ADDISONWESLEY

Upper Saddle River, NJ Boston Indianapolis San Francisco
New York Toronto Montral London Munich Paris Madrid
Capetown Sydney Tokyo Singapore Mexico City

TeX is a trademark of the American Mathematical Society

METAFONT is a trademark of AddisonWesley

The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein.

The publisher offers excellent discounts on this book when ordered in quantity for bulk purposes or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding interests. For more information, please contact:

U.S. Corporate and Government Sales (800) 3823419

For sales outside the U.S., please contact:

International Sales

Visit us on the Web: informit.com/aw

Library of Congress Cataloging-in-Publication Data

Knuth, Donald Ervin, 1938
The art of computer programming / Donald Ervin Knuth.
xiv,782 p. 24 cm.
Includes bibliographical references and index.
Contents: v. 1. Fundamental algorithms. -- v. 2. Seminumerical
algorithms. -- v. 3. Sorting and searching. -- v. 4a. Combinatorial
algorithms, part 1.
Contents: v. 3. Sorting and searching. -- 2nd ed.
ISBN 978-0-201-89683-1 (v. 1, 3rd ed.)
ISBN 978-0-201-89684-8 (v. 2, 3rd ed.)
ISBN 978-0-201-89685-5 (v. 3, 2nd ed.)
ISBN 978-0-201-03804-0 (v. 4a)
1. Electronic digital computers--Programming. 2. Computer
algorithms. I. Title.
QA76.6.K64 1997
005.1--DC21 97-2147

Internet page http://www-cs-faculty.stanford.edu/~knuth/taocp.html contains current information about this book and related books.

Electronic version by Mathematical Sciences Publishers (MSP), http://msp.org

Copyright 1998 by AddisonWesley

All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permissions, write to:

Pearson Education, Inc.
Rights and Contracts Department
501 Boylston Street, Suite 900
Boston, MA 02116 Fax: (617) 671-3447

ISBN-13 978-0-201-89685-5
ISBN-10 0-201-89685-0

First digital release, June 2014

Cookery is become an art,
a noble science;
cooks are gentlemen.

TITUS LIVIUS, Ab Urbe Condita XXXIX.vi
(Robert Burton, Anatomy of Melancholy 1.2.2.2)

This book forms a natural sequel to the material on information structures in Chapter 2 of Volume 1, because it adds the concept of linearly ordered data to the other basic structural ideas.

The title Sorting and Searching may sound as if this book is only for those systems programmers who are concerned with the preparation of general-purpose sorting routines or applications to information retrieval. But in fact the area of sorting and searching provides an ideal framework for discussing a wide variety of important general issues:

How are good algorithms discovered?

How can given algorithms and programs be improved?

How can the efficiency of algorithms be analyzed mathematically?

How can a person choose rationally between different algorithms for the same task?

In what senses can algorithms be proved best possible?

How does the theory of computing interact with practical considerations?

How can external memories like tapes, drums, or disks be used efficiently with large databases?

Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!

This volume comprises ).

Like Volumes 1 and 2, this book includes a lot of material that does not appear in other publications. Many people have kindly written to me about their ideas, or spoken to me about them, and I hope that I have not distorted the material too badly when I have presented it in my own words.

I have not had time to search the patent literature systematically; indeed, I decry the current tendency to seek patents on algorithms (see ). If somebody sends me a copy of a relevant patent not presently cited in this book, I will dutifully refer to it in future editions. However, I want to encourage people to continue the centuries-old mathematical tradition of putting newly discovered algorithms into the public domain. There are better ways to earn a living than to prevent other people from making use of ones contributions to computer science.

Before I retired from teaching, I used this book as a text for a students second course in data structures, at the junior-to-graduate level, omitting most of the mathematical material. I also used the mathematical portions of this book as the basis for graduate-level courses in the analysis of algorithms, emphasizing especially , together with Sections 4.3.3, 4.6.3, and 4.6.4 of Volume 2.

For the most part this book is self-contained, except for occasional discussions relating to the MIX computer explained in Volume 1. contains a summary of the mathematical notations used, some of which are a little different from those found in traditional mathematics books.

This new edition matches the third editions of Volumes 1 and 2, in which I have been able to celebrate the completion of TeX and METAFONT by applying those systems to the publications they were designed for.

The conversion to electronic format has given me the opportunity to go over every word of the text and every punctuation mark. Ive tried to retain the youthful exuberance of my original sentences while perhaps adding some more mature judgment. Dozens of new exercises have been added; dozens of old exercises have been given new and improved answers. Changes appear everywhere, but most significantly in (about multidimensional trees and tries).