Sorting linked list

[Badri Lokanathan]

In article <669 at bentley.UUCP> mdr at 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.