Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site siemens.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!princeton!siemens!haahr
From: haahr@siemens.UUCP (Paul Haahr)
Newsgroups: net.math
Subject: Sorting a sorted list by a different order of keys
Message-ID: <107@siemens.UUCP>
Date: Fri, 7-Jun-85 14:45:29 EDT
Article-I.D.: siemens.107
Posted: Fri Jun  7 14:45:29 1985
Date-Received: Sat, 8-Jun-85 03:38:05 EDT
Organization: Siemens RTL Princeton, NJ
Lines: 13

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