Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!umcp-cs!chris
From: chris@umcp-cs.UUCP (Chris Torek)
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <573@umcp-cs.UUCP>
Date: Thu, 27-Mar-86 23:59:04 EST
Article-I.D.: umcp-cs.573
Posted: Thu Mar 27 23:59:04 1986
Date-Received: Sat, 29-Mar-86 16:17:47 EST
References: <669@bentley.UUCP>
Reply-To: chris@maryland.UUCP (Chris Torek)
Organization: U of Maryland, Computer Science Dept., College Park, MD
Lines: 33

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

This method will work.  Unfortunately, its average performance is
O(n^2).  Given an n-element list, you sort it by sorting the n-1
element list, then inserting the first element in place.  The
insertion will, on the average---assuming a random distribution of
values---search through n/2 list elements before finding the
insertion point.  This gives a recurrence relation as follows:

	T(n) = T(n-1) + n/2

Expanding and using T(0) as the base case we get

	T(n) = 1/2 sum {i from 0 to n} i

	     = 1/2 (n * (n+1) / 2)

	     = 1/4 n^2

which is O(n^2).  Heap and merge sorts are O(n log n).

(Technically, you have neglected stack space as well: you will use
O(n) stack frames in your sort.  The heap and merge sorts use only
O(log n) frames.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1415)
UUCP:	seismo!umcp-cs!chris
CSNet:	chris@umcp-cs		ARPA:	chris@mimsy.umd.edu