I Found My Name in macOS
I went looking for a sorting routine I helped write for BSD as a Berkeley undergraduate. Apple still carries its descendant, contributor line intact.
Daniel L. Lu, Aerial View of Apple Park, 2018. CC BY SA 4.0, via Wikimedia Commons.
I went looking for some old code recently, expecting to find nothing at all. What I found instead was my name, sitting in Apple's source tree.
The file lives at stdlib/FreeBSD/heapsort.c in Apple's open source Libc, the C library that ships with macOS, and it has ridden along there through release after release. The copyright belongs to the Regents of the University of California and carries 2 dates, 1991 and 1993. Directly under it, the header records that the code derives from software contributed to Berkeley by "Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias." A few lines further down, Apple's copies still carry the Berkeley version stamp the whole tree received at 4.4BSD, heapsort.c 8.1, dated 6/4/93. I was an undergraduate in applied mathematics then, taking a computer science course on algorithms, and I had assumed, without ever quite examining the assumption, that the work had gone wherever old coursework goes.
The last entry in this series ended by promising this one. That entry was about a bathroom scale, an algorithm hidden inside an object, making decisions about which of its own measurements to believe before it shows you a number. heapsort() is the same kind of hidden machinery moved 1 layer down, into the operating system itself, where the decisions are made once by 3 people and then quietly inherited by everyone who builds on top.
What the routine actually does
Sorting is the most studied problem in computer science, and heap sort is 1 of the handful of answers every programmer learns. It rests on a structure called a heap: values arranged in a plain array so that each element is at least as large as the 2 sitting below it, with position doing the work that pointers would otherwise do and no second copy of the data anywhere. Sorting is then mechanical. Take the top element, swap it to the end where it belongs, and repair what remains by letting the displaced value sift down past its larger child. Each repair costs about log N steps and there are N elements to place, so the procedure runs on the order of N log N. The bound holds in every case rather than on average, so the worst input anyone can construct costs no more than the best.
The comments at the top of the Berkeley file cite Knuth and state that guarantee in a single blunt line. The optimization we spent effort on sits in the same comments: a naive sift spends 2 comparisons per level, 1 to find the larger child and 1 to decide whether to stop there, so drop the second, let the hole run to the bottom, then walk it back up to where the displaced value belongs. The source puts the saving at 15% to 20% in the average case, which matters because the comparison in a library sort is not a machine instruction. It is a function the caller supplies, and it might be weighing 2 integers or 2 database records with 40 fields apiece.
A 1964 idea, a 1993 file, 2 live descendants
We did not invent any of it. J. W. J. Williams published Algorithm 232 in Communications of the ACM in June 1964, introducing both the sort and the binary heap as a structure worth having on its own. Robert Floyd published an efficient refinement that December, and the version programmers recognize today owes as much to Floyd's implementation as to Williams's idea. What the 3 of us contributed was something narrower and more ordinary: a tested, documented, optimized implementation for a C library that other people's programs would call without ever reading.
The path from there to here is not short. Berkeley's Computer Systems Research Group released it, FreeBSD inherited the tree, Apple imported Libc from FreeBSD, and the routine now lives in 2 lineages rather than 1. FreeBSD's current source carries the same header under a modern license identifier, with a 2014 copyright added by David Chisnall for the block-based variant, and FreeBSD 15 still documents heapsort() as part of the Standard C Library. Apple's tree serves an operating system nobody involved had any reason to imagine. The header survived every one of those transfers. So did the Knuth citations, and so did the 15% estimate, and so did the 3 names.
Notice what the header does not say. It does not say the code is ours. The copyright belongs to the Regents of the University of California, and the contribution line is exactly that, a credit: the code derives from software contributed to Berkeley by 3 named people. Ownership and authorship came apart at the moment of contribution, which is the only reason a piece of coursework could travel this far. We had nothing to license. The university did, and the university licensed it to everybody.
The terms then moved on without us. Apple's copies still carry the original 4-clause Berkeley license, including the requirement that advertising for any product built on the code acknowledge the University of California and its contributors. Berkeley deleted that clause on July 22, 1999, in a letter from the director of its Office of Technology Licensing, and FreeBSD's copy of the same file now carries a modern 3-clause identifier instead. One routine, identical code, identical credit, 2 sets of legal terms, depending on which descendant you open. The credit is the part that proved durable, because removing it would be both rude and illegal, and because nothing about the problem the code solves has changed. Frameworks turn over in 5 years and applications get rewritten every decade, but the bottom of the stack has the half-life of infrastructure.
Why this one survived
Heap sort is usually not the fastest way to sort, and the BSD manual page says so in plain language: "Normally, qsort() is faster than mergesort() is faster than heapsort()." Quicksort has better constant factors and friendlier memory access, and on typical data it finishes first. Mergesort returns equal elements in the order it received them, and wants a scratch buffer about as large as the data. Heap sort promises nothing about equal elements and asks the allocator for a single element's worth of space, which is about as close to nothing as a general sort gets.
The file is blunter about that than I would be. Its comments concede that the small memory requirement is the only advantage on offer, then go further: BSD's quicksort picks its pivot by median selection, so the chance of hitting the quadratic worst case is declared nonexistent. The manual page still says the same thing. Then in 1999 Doug McIlroy published an adversary that watches the comparisons a quicksort makes and hands back input built to defeat exactly that defense. The trick works because a library sort does not compare values itself; it calls a comparison function the caller supplies, and a caller who wants to can lie with it. The comment sits there today, confident and unrevised, a generation after somebody showed the confidence was misplaced.
Which is the better reason the routine stayed. Heap sort's worst case is its average case and it sorts in place, so a caller taking input from somewhere it does not control gets a ceiling rather than a hope. Quicksort answers the question "how fast is this usually?" Heap sort answers "what can you promise a caller you have never met?" A library reached from kernel code, embedded systems, and programs whose authors cannot predict their own inputs needs both answers on the shelf.
Sorting, again
I have become interested in sorting again, from a direction that would have made no sense to me at Berkeley. The old question was how to make a machine sort reliably and efficiently, and classical computer science answered it about as thoroughly as any question has been answered. Deterministic, provable, bounded in time and space, running billions of times a day without incident. The new question runs the other way. A benchmark called SortBench, published last year, handed ordinary lists to 7 of the leading models of the day and found that sorting presses on the things these systems are weakest at: staying faithful to the input, comparing values rather than associating them, and keeping the syntax of a list separate from what the items mean. Every model tested dropped items and invented new ones as the lists grew longer. The strongest reasoning model in the set sorted well until the task mixed syntax with meaning, at which point asking it to sort numbers written out as words was enough to break it.
None of that says the models cannot sort, and the paper is careful on the point: given a short list, they all can. What interests me is where the reliability goes as the task grows, and whether the failures are an artifact of producing long output or something structural in how these systems hold relations between items. One line of current work has gone back to running a classical algorithm and calling the model only to compare 2 items at a time, which puts the deterministic procedure back in charge and asks the model for judgment alone.
A problem computing solved decisively in the 1960s has become a diagnostic for the most capable systems built since. The task got easier for computers and harder for our theories of intelligence, and I intend to come back to it properly in a later entry.
For now the circle is enough. An idea published in 1964 reached Berkeley, passed through 3 contributors and into BSD, traveled through FreeBSD into Apple's source tree, and waited there with the header intact until I went looking. I once worked on the question of how machines sort, and what interests me now is what it means when they cannot.
Next in the series: why a system that can write a proof still struggles to put 50 numbers in order.
Further Reading
From this blog
- I Weigh How Much? - the first entry in this series, on the judgments a scale's firmware makes before it shows you a number.
Sources
- heapsort.c, Apple Libc, stdlib/FreeBSD - the file in Apple's open source C library, carried across releases from Libc-167 to the present. Source of the 1991 and 1993 Berkeley copyright, the contributor attribution, the 8.1 release stamp dated 6/4/93, the Knuth citations, the median-selection comment, and the 15% to 20% estimate.
- heapsort.c, FreeBSD, lib/libc/stdlib - the second living lineage. Same attribution, now under an SPDX license identifier with David T. Chisnall's 2014 copyright for the block variant.
- heapsort(3) manual page, FreeBSD - the 3 BSD sorting functions documented together. Source of the relative speed sentence, the stability distinction, and the "almost no additional memory" characterization. Note that OpenBSD's wording of the same sentence differs slightly.
- The BSD advertising clause rescission, July 22, 1999 - William Hoskins, Office of Technology Licensing, UC Berkeley, deleting clause 3 for all Regents-copyrighted BSD files.
- CSRG Members, Supporters, and Contributors - NetBSD's reproduction of the Berkeley contributor list, with the
heapsort(3)entries for Elmer Yglesias, Kevin Lew, and Ronnie Kon. - McIlroy, M. D. (1999). A Killer Adversary for Quicksort - Software: Practice and Experience 29(4), 341-344. The comparison-function adversary that defeats median selection.
- Williams, J. W. J. (1964). "Algorithm 232: Heapsort." Communications of the ACM 7(6), 347-348. The original.
- Floyd, R. W. (1964). "Algorithm 245: Treesort." Communications of the ACM 7(12), 701. The refinement published that December.
- Knuth, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching. Section 5.2.3, and the exercise behind the comparison-saving sift.
- Herbold, S. (2025). SortBench: Benchmarking LLMs based on their ability to sort lists - arXiv 2504.08312. The 7 model evaluation, the faithfulness failures on long lists, and the numbers-written-as-words result.
- Verbalized Algorithms - arXiv 2509.08150. Classical algorithm in control, model used as a comparison oracle.
AI Assistance Statement ▾
This blog publishes at a near daily rate, and that pace is possible because AI tools do a substantial share of the work between the idea and the published text. Preparation of this entry included assistance from Anthropic's Claude and from OpenAI's ChatGPT (GPT-5 series reasoning models). I use them to research a topic and gather primary sources, to organize ideas and propose structure, to draft and revise prose, to check factual claims against the cited sources before publication, and to score drafts against a set of house style rules. Longer pieces are often developed across several sessions. A written handover carries the argument, sources, and open questions from one session to the next, and the same tools help prepare those handovers. The tools also help identify candidate images and confirm that selected images appear to be released for reuse, for example through public domain or Creative Commons licensing.
The process is also an AI experiment in its own right. There is a live argument about what AI-assisted writing does to originality, and whether the result is thought or slop; the August 2026 dispute over a Wall Street Journal op-ed that its author acknowledged drafting with AI, and the Journal's subsequent defense of the practice (WSJ is behind a paywall, but for a public summary: click here, and here), is one newsworthy example. I would rather run the experiment openly than pretend it is not happening. This blog is one sustained attempt to find out whether a person with an argument, working with these tools every day, produces writing that is still recognizably that person's, and I disclose the method so readers can judge the result.
The judgment is mine. I choose the topic, decide the argument, supply the personal and professional experience the pieces draw on, read and edit every draft, verify the sources and image licensing, and take full responsibility for the final published content. Where a post contains my own recollections, the AI did not invent them.
Statement revised September 2026.