Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!mit-eddie!uw-beaver!tektronix!reed!psu-cs!omepd!mipos3!cpocd2!howard
From: howard@cpocd2.UUCP (Howard A. Landman)
Newsgroups: comp.edu,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <472@cpocd2.UUCP>
Date: Wed, 4-Mar-87 18:35:22 EST
Article-I.D.: cpocd2.472
Posted: Wed Mar  4 18:35:22 1987
Date-Received: Sun, 8-Mar-87 01:38:30 EST
References: <814@fmsrl7.UUCP>
Reply-To: howard@cpocd2.UUCP (Howard A. Landman)
Distribution: world
Organization: Intel Corp. ASIC Services Organization, Chandler AZ
Lines: 43
Xref: mnetor comp.edu:147 sci.research:68

In article <814@fmsrl7.UUCP> wayne@fmsrl7.UUCP (Michael R. Wayne) writes:
>	I need information on how to share a discovery with others in
>the computer science profession.  I have an algorithm which implements
>an order(N) sort (ie the search time is linear with respect to the
>number of items with a constant overhead).  I seem to remember that
>someone "proved" that this could not be done and I do not have any
>information handy on this.
>
>	3)  Has this problem already been solved?  If so, pointers to
>	this would also be appreciated (since no one I talked to knew
>	about the solution).
>
>Additional info:
>	In order to implement the sort, the key must be completely
>	specified.  This means that the sort is data dependent
>	Examples of complete key specification:
>		9 digits (ie SS#)
>		20-80 ASCII characters
>	Does this invalidate the algorithm?
>	Of course, the sort time IS dependent on the size of the key
>	(After all, how can a 5 character key and a 5000 character
>	key take the same amount of time to compare?
>	The algorithm need not be very memory intensive.  I see no reason
>	why thousands of records with 200 character keys could not be done
>	on a Z-80 CP/M machine.

Sounds like you've reinvented distribution sort or partitioning sort.
Both of these classes of algorithms can appear O(N)*O(K), where K is
the length of the key.  But guess what?  If every element can have a
unique key, then the length of the key must grow as O(log N) as N increases.
This results in an asymptotic complexity of O(N log N), just as you
would expect.

This is not to say that these algorithms cannot be useful in practice.
In fact, IBM punched-card sorters can be considered as mechanical examples
of distribution sort.  The real question is: can your algorithm outperform
commercial sorting algorithms on commercial workloads?  If so, you can make
a bundle, because a sizeable fraction of business computing is just sorting
large files (over 50% at many sites).
-- 

	Howard A. Landman
	...!intelca!mipos3!cpocd2!howard