Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site sftri.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!mhuxm!sftig!sftri!jss
From: jss@sftri.UUCP (J.S.Schwarz)
Newsgroups: net.math
Subject: Re: Sorting a sorted list by a different order of keys
Message-ID: <455@sftri.UUCP>
Date: Sun, 9-Jun-85 14:54:53 EDT
Article-I.D.: sftri.455
Posted: Sun Jun  9 14:54:53 1985
Date-Received: Mon, 10-Jun-85 08:27:08 EDT
References: <107@siemens.UUCP>
Organization: AT&T Bell Laboratories, Summit N.J.
Lines: 12

>
> 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?  
> 			-- Paul Haahr
> 			..!{allegra,ihnp4}!princeton!{jendeh,siemens}!haahr

Not in general.  If all key values are distinct then knowing that the
list is sorted by k1 gives no information about the order when
sorted by k2.

Jerry Schwarz
ihnp4!attunix!jss