Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!talcott!harvard!seismo!brl-adm!brl-smoke!gwyn
From: gwyn@brl-smoke.ARPA (Doug Gwyn )
Newsgroups: net.lang.c
Subject: Re: Sorting linked lists
Message-ID: <1945@brl-smoke.ARPA>
Date: Wed, 19-Mar-86 23:56:52 EST
Article-I.D.: brl-smok.1945
Posted: Wed Mar 19 23:56:52 1986
Date-Received: Sat, 22-Mar-86 23:53:20 EST
References: <165@ablnc.UUCP>
Reply-To: gwyn@brl.ARPA
Organization: Ballistic Research Lab (BRL)
Lines: 13

In article <165@ablnc.UUCP> rcpilz@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!)