Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!bellcore!faline!sabre!zeta!mb2c!fmsrl7!wayne
From: wayne@fmsrl7.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc
Subject: Information on order(N) sort
Message-ID: <814@fmsrl7.UUCP>
Date: Mon, 23-Feb-87 21:02:06 EST
Article-I.D.: fmsrl7.814
Posted: Mon Feb 23 21:02:06 1987
Date-Received: Fri, 27-Feb-87 01:17:57 EST
Reply-To: wayne@fmsrl7.UUCP (Michael R. Wayne)
Distribution: world
Organization: Ford Motor Company, Scientific Research Labs, Dearborn, MI
Lines: 48
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:108 comp.lang.misc:276 comp.os.misc:26
Bcc: wayne


	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.  (Back in my college days, my professor
and I did not see eye-to-eye and he threw me out of my data structures
class.)  I really need a couple of things:

	1)  Could someone point me to the this "proof" so that I can
	refute it.  I think I know which part would be invalid but I
	would like to make sure.  Mail containing the proof would be
	great.
	2)  Being a mercenary (after all, consultant is just a
	euphemism), I would like to exploit this.  Before you flame me,
	you should note that I am not looking for $, just where/how I
	let people know and how I get some sort of credit for this.
	Should I go through a University? (CACM comes to mind but I've
	let my subscription lapse in recent years and donated all my
	back issues to the library.  I'm not sure they would accept
	a paper from me anyway).  Suggestions as to what I should ask
	for would be appreciated.
	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.

Please mail responses as I do not subscribe to all these newsgroups.
-- 
===== Your life is your own fault! ============== Rebel or be oppressed! =====
Michael R. Wayne    (313) 322-3986     UUCP: {epsilon|ihnp4}!mb2c!fmsrl7!wayne
Working at (but not employed by) Ford Motor Company  ** This space for rent **
Since I am an independent consultant, the above opinions ARE my employers.
===== Are your moral/ethical/religious/political beliefs really rational? ====