Sorting linked list

[KW Heuer]

In article <2516 at utcsri.UUCP> utcsri!greg (Gregory Smith) writes:
>What it should do next is .., call itself recursively to sort the shortest
>list.  It should then *loop back* to sort the longest list (if it is more
>than one item).  Thus a stack frame is saved while sorting the longer one.

A good optimizer should compile tail-recursion into a jump anyway.  (But
there are few good optimizers by that standard.)

>Also: write this as a separate function which calls itself recursively,
>and then call that non-recursively from the actual sort function. That
>way things like the 'compare' function address which do not change
>during a sort can be stuffed into an extern and will not need to be
>passed to each call....  Use as few auto (as opposed to static) variables
>as you can get away with....

Although this does reduce the stack space and presumably the execution
time, it also makes it non-reentrant.  I have no objections to anyone who
wants to write this routine as described, but the non-reentrancy should be
mentioned under BUGS or WARNINGS.

Sometimes when I have to write a recursive routine, I code it in assembler
using the primitive procedure-calling mechanism (bsb-rsb on the vax), with
arguments in fixed registers, and enclose it in a C-callable envelope.  That
way it's both reentrant AND fast (and I keep a C version for portability).

Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint