[Animats]

There is a much better discussion of this in vol. I of Knuth.

(Amusingly, in the original edition Knuth uses a simple algorithm (linking the allocated spaces) in the text and leaves the better algorithm (linking the free spaces) to an exercise. In Unix V6 (yes, this really dates me), the "malloc" in the C library used the simple algorithm from Knuth, variable names and all, causing O(N^2) performance problems.)

[djdjenej]

Fascinating---do you have a pointer to the story or some discriminating keywords?

[carussell]

Here go: http://tech.slashdot.org/comments.pl?sid=26793&cid=2895270