Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 ggr 10/10/85; site bentley.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!bentley!kwh
From: kwh@bentley.UUCP (KW Heuer)
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <695@bentley.UUCP>
Date: Sun, 6-Apr-86 18:54:52 EST
Article-I.D.: bentley.695
Posted: Sun Apr  6 18:54:52 1986
Date-Received: Wed, 9-Apr-86 20:32:14 EST
References: <669@bentley.UUCP>, <139200023@uiucdcsb>
Organization: AT&T Bell Laboratories, Liberty Corner
Lines: 25

In article <139200023@uiucdcsb> mccaugh@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