---
title: "The Art of Computer Programming, Volume 3: Sorting and Searching"
authors:
  - "Donald E. Knuth"
year: 1973
venue: "Addison-Wesley"
arxiv: null
doi: null
source: "https://www-cs-faculty.stanford.edu/~knuth/taocp.html"
topics:
  - sorting
  - searching
  - knuth
  - taocp
seed_rank: 597
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "systems"
relevance_score: 9
lineage: foundations-of-computing
cites:
  - title: "The Art of Computer Programming, Volume 1: Fundamental Algorithms"
    url: "https://www-cs-faculty.stanford.edu/~knuth/taocp.html"
    year: 1968
    arxiv: null
    doi: null
  - title: "The Art of Computer Programming, Volume 2: Seminumerical Algorithms"
    url: "https://www-cs-faculty.stanford.edu/~knuth/taocp.html"
    year: 1969
    arxiv: null
    doi: null
see:
  - "595-the-art-of-computer-programming-volume-1-fundamental-algorit"
  - "596-the-art-of-computer-programming-volume-2-seminumerical-algor"
---

# The Art of Computer Programming, Volume 3: Sorting and Searching

## One-sentence takeaway

TAOCP Volume 3 is the encyclopedic analysis of internal/external sorting, selection, and searching, including hashing and balanced trees.

## Why it matters here

ECS queries, spatial indexes, and asset catalogs are sorting/searching problems. This 1973 volume is the default depth cite before claiming a new structure.

## Key ideas

- Combinatorial analysis of insertion, exchange, selection, merging, and distribution sorts, with exact leading terms.
- External sorting (multiway merge, replacement selection) treats memory hierarchy as part of the algorithm.
- Searching: digital trees, balanced trees, hashing, and the analysis of collisions and occupancy.
- First edition Addison-Wesley 1973; later editions add newer structures without abandoning the catalog method.
- Completes the original three-volume core of TAOCP with Volumes 1 and 2.

## Caveats

## Links

- URL: https://www-cs-faculty.stanford.edu/~knuth/taocp.html