Sorting linked list

[Chris Torek]

In article <669 at bentley.UUCP> mdr at 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 at umcp-cs		ARPA:	chris at mimsy.umd.edu