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: bobduff@world.std.com (Robert A Duff)
Subject: Re: Anyone help develop an algorythm?
Date: 1997/04/20
Message-ID: <E8yGpJ.Dyu@world.std.com>#1/1
X-Deja-AN: 236203592
References: <5jddg7$uf0@newssvr01-int.news.prodigy.com>
Organization: The World Public Access UNIX, Brookline, MA
Newsgroups: comp.lang.ada
Date: 1997-04-20T00:00:00+00:00
List-Id: <comp.lang.ada>


In article <5jddg7$uf0@newssvr01-int.news.prodigy.com>,
Matthew Givens <NKSW39B@prodigy.com> wrote:
>I have a linked list, each node corresponding to an array (contiguous in 
>memory) of fixed length strings. ...

Perhaps you should construct an array on the side, containing pointers
to all the strings.  Then sort that, using your favorite (fast) sorting
algorithm.

Constructing the array can be done in linear time.  You can walk the
list once to determine the size of the array.  Or perhaps your program
already knows the size.  Or perhaps it knows some reasonable upper bound
on the size.  Then walk the list again, putting pointers to each string
in the array.  (The strings need to be "aliased".)  Then do the sort.

- Bob