Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site brl-tgr.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!philabs!cmcl2!seismo!brl-tgr!gwyn
From: gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>)
Newsgroups: net.math
Subject: Re: Sorting a sorted list by a different order of keys
Message-ID: <11286@brl-tgr.ARPA>
Date: Mon, 17-Jun-85 18:47:03 EDT
Article-I.D.: brl-tgr.11286
Posted: Mon Jun 17 18:47:03 1985
Date-Received: Thu, 20-Jun-85 20:02:20 EDT
References: <7298@watdaisy.UUCP>
Organization: Ballistic Research Lab
Lines: 11

> In article <11259@brl-tgr.ARPA> gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) writes:
> >[.....]
> >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.