Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!harvard!uwvax!topaz!bentley!kwh
From: kwh@bentley.UUCP (KW Heuer)
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <708@bentley.UUCP>
Date: Fri, 11-Apr-86 15:08:13 EST
Article-I.D.: bentley.708
Posted: Fri Apr 11 15:08:13 1986
Date-Received: Sun, 13-Apr-86 08:11:10 EST
References: <2516@utcsri.UUCP>
Organization: AT&T Bell Laboratories, Liberty Corner
Lines: 26

In article <2516@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