Sorting and searching
by Donald Knuth · first published 1973
40% recommend60% neutral
Why HN recommends it
Deep, rigorous treatment of sorting and searching algorithms, including hashing and tape sorting. It serves as an in-depth reference for working engineers and for anyone studying algorithms seriously.
Summarised by Claude from recommending comments
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2007–2026The art of computer programming
Donald Knuth
Recommended by 336 · mentioned by 1,125336 recommend · 1,125 mention336 recommend · 1,125336 recommend
2015–2023The MMIX Supplement
Martin Ruckert
Recommended by 1 · mentioned by 51 recommend · 5 mention1 recommend · 51 recommend
2014–2023The magic garden explained
Berny Goodheart
Recommended by 3 · mentioned by 63 recommend · 6 mention3 recommend · 63 recommend
2011–2022Linear programming
Vašek Chvátal
Recommended by 5 · mentioned by 65 recommend · 6 mention5 recommend · 65 recommend
2008–2024Theory of computation
Michael Sipser
Recommended by 14 · mentioned by 1914 recommend · 19 mention14 recommend · 1914 recommend
2010–2025The art and theory of dynamic programming
Stuart E. Dreyfus
Recommended by 1 · mentioned by 41 recommend · 4 mention1 recommend · 41 recommend
2010–2025Introduction to functional programming
Bird, Richard
Recommended by 7 · mentioned by 97 recommend · 9 mention7 recommend · 97 recommend
2012–2023Flow-based programming
J. Paul Morrison
Recommended by 5 · mentioned by 125 recommend · 12 mention5 recommend · 125 recommend
…study CS, but I did read several books on algorithms. Especially notable is the seven-volume work "The Art of Computer Programming" by Donald Knuth; in particular the volumes "Fundamental Algorithms", "Sorting and Searching", and "Seminumerical Algorithms" are timeless masterpieces, entertaining and witty, and they totally nail their subject-matter. If you think CS is equivalent to "algorithms", then read these books. N.B.…
on “Ask HN: What book to read to get a footing in CS theory?” ↗I would recommend "Sorting and Searching" Volume 3 from Donald Knuth's "The Art of Computer Programming". Fantastic, in-depth read.
on “Ask HN: What language-agnostic programming books should I read?” ↗…Such a guarantee is essentially a theorem in applied math called computer science. A good example of how to prove such theorems is, of course, in D. Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching. Again, I have been happy just to use heap sort and forget about looking for anything faster on average.
on “A Killer Adversary for Quicksort (1999) [pdf]” ↗…the essential computer science, write some code in some common procedural programming language for some simple exercises, check out at the library D. Knuth's The Art of Computer Programming, Volume 3, Sorting and Searching, learn about big-O notation, the heap data structure and heap sort, as an exercise program, say, a priority queue based on the heap data structure, learn about the Gleason bound and how heap sort achieves it…
on “Confession as an AI researcher; seeking advice” ↗…become got me to download Lisp in a Box and then buy the used copy. Currently visiting, this book orbits in and out of the rotation with a cometary periodicity. + Art of Computer Programming: Volume 3, Sorting and Searching Twenty-five years ago or so I bought volume I and about 15 years I donated it to the community radio station's books sale [WMNF 88.5]. I spent about $25 dollars including shipping for used copies of the…
on “Ask HN: What's the best programming book you've read recently?” ↗Knuth, The Art Of Computer Programming V3, Sorting & Searching covered both multiply & shift and modulo prime integer hashing in some detail in its first edition written in the 1960s, published in 1973. While not "modern", Knuth has always been a bona fide classic, especially as regards hashing, and should really be cited by this survey paper, IMO. (EDIT: people now call this "Fibonacci Hashing"
on “High Speed Hashing for Integers and Strings (2015)” ↗…I got an A+. I barely scraped through with a C for Engineering Math (Differential Equations). For me, the teacher made the difference in math. For CS, the most influential books for me were Knuth, Sorting and Searching (although I actually bought all three books in the series, unlike most others I knew), as well as the original Kernighan & Ritchie book on the C programming language (before ANSI C was published).
on “Ask HN: The book that did it for you in math and/or CS?” ↗…functionality modern programmer should be calling from a library, not implementing by hand. But I think it's hugely enriching to read these books. I read 1-3 back in the 70s, and was particularly inspired by Sorting and Searching, and especially the chapter on random numbers. RNGs have intrigued me ever since. I find Knuth's writing style very pleasant. He's funny. So is it worth the time and effort? Not if "worth it" means "makes…
on “Ask HN: Is Knuth's TAOCP worth the time and effort? (2023)” ↗…http://amzn.to/2qTu86F Programming Pearls, Bentley http://amzn.to/2sIRPe9 Software Process Design: Out of the Tar Pit, McGraw-Hill http://amzn.to/2rVX0v0 Software Runaways, Glass http://amzn.to/2qT2mHn Sorting and Searching, Knuth http://amzn.to/2qQ4NWQ Structure and Interpretation of Computer Programs, Abelson and Sussman http://amzn.to/2qTflsk The Art of Unit Testing, Manning http://amzn.to/2rsERDu The Art of Unix Programming,…
on “Ask HN: What language-agnostic programming books should I read?” ↗…area of endeavor within computer science. It's a great work (I'd be lying if I'd said I'd poured into the entirety of it extensively, but I've spent weeks on certain portions, like the MMIX fascicle and Sorting and Searching), but PAIP has a significantly better claim at "kickstarting" the "read code instead of write it" trend, because in TAOCP the code doesn't take center stage, and it was never the point for it to (hence…
on “Peter Norvig Joins Stanford HAI” ↗…referred to it on occasion when people say things like, "if we seed the random number generator, take the random number, then feed that into the seed, the result would be more random." I read most of Vol 3, Sorting and Searching, when applying for jobs. It was more interesting than leetcode grinding. I don't know if it was more useful, but it was better for my sanity.
on “Knuth's Art of Computer Programming, V 4B, has gone into print” ↗Just read his introduction to generating pseudo-random numbers or his sketch of a proof of Benfords law in Seminumerical Algorithms. Excellent stuff. For moderately impractical, look at tape sorting in Sorting and Searching.
on “Ask HN: Most interesting, mildly impractical, well-written books on software?” ↗What's the problem? From D. Knuth's The Art of Computer Programming: Sorting and Searching, (1) if sorting n records by comparing pairs of keys, then the Gleason bound shows that on average can't sort faster than O( n ln(n) ). (2) Heap sort sorts n records in both worst case and average…
on “A Killer Adversary for Quicksort (1999) [pdf]” ↗…productive. The person needs to know how to read with understanding, learn, analyze, and create meaning by writing English. So, in interviewing, I want such a person. 'Dynamic programming' and Knuth's 'Sorting and Searching' or 'functional programming'? I don't care. How 'bout that!
on “Programmer Competency Matrix: Do you use it when hiring?” ↗…keeping the tree balanced while making the changes and doing so with relatively fast worst case running time was a challenge. One solution was AVL trees (see D. Knuth's The Art of Computer Programming: Sorting and Searching or more recent books listed in this thread) and, mostly for data stored on disk, B-trees. Actually there are several important, that is, relatively fast, algorithms for manipulating trees. Early on…
on “Ask HN: What book to read to get a footing in CS theory?” ↗