Sorting linked lists

[Doug Gwyn]

In article <165 at ablnc.UUCP> rcpilz at ablnc.UUCP (Robert C. Pilz) writes:
>I would like some advice on sorting linked lists.

I believe the "list merge" sorting algorithm described in
Knuth Vol. 3 can be adapted to this case.  Since it works
by changing link fields, rather than by actually moving
records, it would not break other pointers in the records.

List merge sorting is one of my favorite in-memory methods,
primarily for its stability (see Knuth for definition).
It was at the heart of an interactive traffic analysis
system I whipped up on a 24Kb paper-tape based CDC 1700.
(Oh, how I miss the good old days!)