From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,50880f040eb869b4
X-Google-Attributes: gid103376,public
From: dewar@merv.cs.nyu.edu (Robert Dewar)
Subject: Re: Anyone help develop an algorythm?
Date: 1997/04/22
Message-ID: <dewar.861719085@merv>#1/1
X-Deja-AN: 236721934
References: <5jddg7$uf0@newssvr01-int.news.prodigy.com>
 <1997Apr20.234419.16075@ocsystems.com>
Organization: New York University
Newsgroups: comp.lang.ada
Date: 1997-04-22T00:00:00+00:00
List-Id: <comp.lang.ada>


Joel says

<<I would be inclined to go with a merge sort (of some kind or other).
Allow me to quote from Robert Sedgewick's _Algorithms_ (I highly
recommend this book).  "Mergesort is the method of choice for sorting
a linked list, where sequential access is the only kind of access
available."  It is quite simple, has O(NlogN) worst-case performance and
in your situation ought to require additional memory of at most 1 array
of strings (plus a teensy bit).  Of course sort each array by any method
you prefer (quicksort, heapsort, shellsort, or selection sort).>>

That seems a kind of confused mixture. If you are going to use merge sort,
use merge sort. you don't need any arrays, and you don't need to use any
other algorithm. The algorithm is trivial, split the list into two halves,
sort each half recursively, and then do a merge, end of story. This has
worst case NlogN and is what Sedgewick means when he makes his suggestion.