Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!mhuxm!mhuxf!mhuxi!mhuhk!mhuxt!houxm!whuxl!whuxlm!akgua!gatech!seismo!brl-adm!brl-smoke!smoke!gwyn@BRL.ARPA
From: gwyn@BRL.ARPA
Newsgroups: net.lang.c
Subject: Re:  Sorting linked list
Message-ID: <2189@brl-smoke.ARPA>
Date: Sat, 29-Mar-86 00:17:54 EST
Article-I.D.: brl-smok.2189
Posted: Sat Mar 29 00:17:54 1986
Date-Received: Tue, 1-Apr-86 07:13:12 EST
Sender: news@brl-smoke.ARPA
Lines: 21

Your method is cute, but it has the following drawbacks:
	It amounts to an insertion sort, with high overhead
	due to the large number of function calls, 2N-1 for
	an N-long list.
	The average number of comparisons for an N-long
	randomly-ordered list is on the order of N(N-1)/4,
	i.e. O(N^2), which is not the best attainable for
	large N.  (At least the function call overhead
	dwindles to insignificance by comparison.)
	Despite your claim, it does require extra space
	(on the run-time stack) proportional to the list size.
This algorithm might be suitable for relatively short lists
where code size is an important factor (e.g. ROM application).

Using recursion like this is good for quick hacks, but for
serious production work nothing beats a good algorithm.
The standard reference for sorting algorithms is Knuth Vol. 3.

P.S.  I did the above math in my head, away from reference
books.  I may be off a factor of two or something similar;
that doesn't affect the argument.