Bookshelf Classic: Beautiful Code
For this post though, I want to focus on Jon Bentley's contribution, curiously titled "The Most Beautiful Code I Never Wrote." Elaborating, Bentley writes
In software, the most beautiful code, the most beautiful functions, and the most beautiful programs are sometimes, not there at all.
He then uses the Quicksort algorithm to illustrate his point, first reviewing the code, instrumenting it with counters, and optimizing it along the way. But the pressing question he tries to answer is: "How many comparisons does Quicksort make, on average, for a random array of size n?"
One could generate large samples of random data, make several trial runs, and get an average, but Bentley takes a different route, a code-less path that crosses into mathematical proofs. I didn't find it easy to follow, and got help from a talk he gave to Google in 2007: Three Beautiful Quicksorts.
In the end, Bentley derives a completely mathematical analysis of Quicksort's behavior. It's wonderful. It's frustrating. It reminds me of an old joke:
A hungry man walks into a diner and sees the special is a Ham Sandwich. "Nothing would be better than a ham sandwich!"
The waitress returns with an empty plate. "What's this?" the man asks.
She replies, "You said 'Nothing would be better than a ham sandwich.' So I gave you Nothing."
The piece doesn't fill the belly, but it does move the mind.
For more on Bentley's work, see my review of his book More Programming Pearls.