Reference counting garbage collection

[Gareth McCaughan]

Tim Peters wrote:

> still-waiting-for-bubblesort's-rehabilitation-ly y'rs  - tim

Knuth volume 3 describes an application where bubble sort
is *optimal*. It's a pretty eccentric one, though. If I
remember correctly, the model is that you have a loop of
tape[1] which can only be moved in one direction, and a
read/write head that can access two adjacent locations,
and maybe some other restrictions carefully engineered to
make bubble sort optimal. I don't know whether the work
Knuth references was done *only* in order to find a way
to declare bubble sort optimal, or whether it's something
someone was interested in for other reasons.


[1] Actually, Knuth describes it in terms of a disc, but
    the term "disc" might be too distracting these days.

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
.sig under construc