Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watdaisy.UUCP
Path: utzoo!watmath!watnot!watdaisy!gjerawlins
From: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Newsgroups: net.math
Subject: Re: Sorting a sorted list by a different order of keys
Message-ID: <7321@watdaisy.UUCP>
Date: Wed, 19-Jun-85 22:49:13 EDT
Article-I.D.: watdaisy.7321
Posted: Wed Jun 19 22:49:13 1985
Date-Received: Thu, 20-Jun-85 10:36:10 EDT
Reply-To: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Organization: U of Waterloo, Ontario
Lines: 32

>>>Actually, there are some sorting methods that are better than N log N;
>> 
>>     Pardon me? Loose lips sink ships, please define your model.
>
>As just an example -- not the best possible algorithm -- consider
>sorting by hashing (O(N) in time and space).  Various obvious
>modifications could make this approach workable.  For practical
>purposes, a good O(N log N) merge sort is just fine.

    I try not to clutter the net with things like this but i wish
to point out that the time bound of any algorithm _depends on your model_.
That was the reason i asked for a definition of the model. I didn't
want people to go away with the notion that nlgn is beatable in
the general case where you know nothing about your data and you
are counting the minimum number of comparisons necessary and
sufficient to transform any permutation of n data items to some
(fixed) permutation of itself.
    There are only three ways to "beat" nlgn. Either you know
something about the distribution of the input prior to running
you algorithm or you decided to count something other than the
number of comparisons of two data elements, or you count something
other than the worst case possible, in all three cases you
have changed the model. Radix sort is a simple example of the 
first type of special case since it won't work unless you know
that the input consists of integers in some prespecified range.
Sorting in parallel using n processors (taking constant time)
is an example of the second. Hash sort is an example of the 
third type since you are concerned with the average case.
	Greg.
-- 
Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo
{allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins