Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.7.0.10 $; site uiucdcsb
Path: utzoo!linus!decvax!bellcore!ulysses!mhuxr!mhuxn!ihnp4!inuxc!pur-ee!uiucdcs!uiucdcsb!mccaugh
From: mccaugh@uiucdcsb.CS.UIUC.EDU
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <139200023@uiucdcsb>
Date: Wed, 2-Apr-86 02:13:00 EST
Article-I.D.: uiucdcsb.139200023
Posted: Wed Apr  2 02:13:00 1986
Date-Received: Sat, 5-Apr-86 05:12:16 EST
References: <669@bentley.UUCP>
Lines: 9
Nf-ID: #R:bentley.UUCP:669:uiucdcsb:139200023:000:343
Nf-From: uiucdcsb.CS.UIUC.EDU!mccaugh    Apr  2 01:13:00 1986


 If you happen to know the size (= no. of nodes) in the linked list), why not:

 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?

    For a list of n > 2 nodes, expected performance will be O(n lg n).