Sorting linked list

[KW Heuer]

In article <139200023 at uiucdcsb> mccaugh at uiucdcsb.CS.UIUC.EDU writes:
>If you happen to know the size (= no. of nodes) in the linked list), why not:

Knowing the length of the list isn't critical, since it can be determined
with an additional O(n) pass, which will be dominated by the qsort.

>1) Make one pre-pass thru the list, initalizing corresponding slots of an
>  "index vector" to the addresses of the nodes; then:
>
>2) use quicksort thru the index vector to sort the list?

Several people have made this suggestion, or a similar one using heapsort.
Like the insertion sort, it's easy (given that qsort() has already been
written!); it has the added advantage of being O(n log n) time.

However, it also consumes O(n) space.  This is undesirable for a general-
purpose library routine.  Presumably it will call malloc() for the array.
What does it do if malloc() fails?  Also, one might want to implement it
using a language/environment that doesn't allow dynamic allocation.

Is it possible to implement a quicksort on a linked list directly?  (Just
wondering; I don't think it would be an improvement on the posted merge
sort, which is already O(n log n) time and O(1) space.)

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