Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: $Revision: 1.6.2.16 $; site inmet.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!cca!inmet!ron
From: ron@inmet.UUCP
Newsgroups: net.math
Subject: Re: Sorting a sorted list by a different
Message-ID: <5700006@inmet.UUCP>
Date: Wed, 19-Jun-85 14:15:00 EDT
Article-I.D.: inmet.5700006
Posted: Wed Jun 19 14:15:00 1985
Date-Received: Sun, 23-Jun-85 02:09:28 EDT
References: <107@siemens.UUCP>
Lines: 16
Nf-ID: #R:siemens:-10700:inmet:5700006:000:605
Nf-From: inmet!ron    Jun 19 14:15:00 1985


/**** inmet:net.math / siemens!haahr /  2:45 pm  Jun  7, 1985 ****/
Given a list sorted by keys k1, k2 is there a fast (i.e., better than
n log n) method for sorting it by keys k2, k1?  A stable sort on k2
(one that preserves order when keys are equal) or merge where each run
is the sequence of values with k1 equal are both n log n.  Is there
anything I'm missing that will take advantage of the fact that the k1's
are already ordered?

			-- Paul Haahr
			..!{allegra,ihnp4}!princeton!{jendeh,siemens}!haahr
-- 

			-- Paul Haahr
			..!{allegra,ihnp4}!princeton!{jendeh,siemens}!haahr
/* ---------- */