Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!rochester!ur-helheim!badri
From: badri@ur-helheim.UUCP (Badri Lokanathan)
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <527@ur-helheim.UUCP>
Date: Fri, 28-Mar-86 10:46:11 EST
Article-I.D.: ur-helhe.527
Posted: Fri Mar 28 10:46:11 1986
Date-Received: Sun, 20-Apr-86 23:58:34 EST
References: <669@bentley.UUCP>
Reply-To: badri@helheim.UUCP (Badri Lokanathan)
Organization: U. of Rochester, EE Dept.
Lines: 22

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 ..........
>
>Voila! Less than tweny lines of code in its entirety.  Think recursive, man!
>
You do not want to use a recursive solution for the following reasons:

1. It involves loads of stack operations, which slow down the process.
2. For each level of recursion you have to retain a snap shot of the
   variables at that call. Thus in reality you do not save any
   memory; you may end up consuming more!
3. There are very efficient iterative sorting algorithms available -
   in fact most sorting algorithms have iterative implementations
   that are NOT long in terms of lines of code.

In any case, I believe, like many others, that the easiest thing to do
is to make use of qsort. If efficiency is of importance then use a good
iterative algorithm and NOT recursion.