Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!lll-crg!lll-lcc!ucdavis!ucbvax!cad!faustus
From: faustus@cad.UUCP (Wayne A. Christopher)
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <117@cad.UUCP>
Date: Thu, 27-Mar-86 19:09:20 EST
Article-I.D.: cad.117
Posted: Thu Mar 27 19:09:20 1986
Date-Received: Sun, 20-Apr-86 12:14:40 EST
References: <669@bentley.UUCP>
Organization: U. C. Berkeley CAD Group
Lines: 21

In article <669@bentley.UUCP>, mdr@bentley.UUCP (M. Rossner) writes:
> It seems that there is an obvious recursive solution to this
> problem that has not yet been mentioned.  To sort a linked list
> (in place, without allocating ANY more memory), I just need to sort
> everything except the first node and then insert the first node into
> this list.

If you're concerned with the amount of space you use, you should be taking
the stack space that your process is using up by all that recursion.  Also
insertion sort isn't the fastest that you can do -- I think making an array,
qsort()'ing it, and re-listing it is the best you can do.  Besides, nowadays
it's not fashonable to be concerned with saving space -- it's all virtual
anyway... :-)

> Voila! Less than tweny lines of code in its entirety.  Think recursive, man!

In C you shouldn't automatically think in terms of recursion, since it is
a lot easier to write fast iterative code.  Recursion is more elegant but
seldom faster.

	Wayne