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: <11259@brl-tgr.ARPA>
Date: Sun, 9-Jun-85 03:23:29 EDT
Article-I.D.: brl-tgr.11259
Posted: Sun Jun  9 03:23:29 1985
Date-Received: Tue, 11-Jun-85 03:13:04 EDT
References: <107@siemens.UUCP>
Organization: Ballistic Research Lab
Lines: 9

> 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

A simple proof that no such general method exists:
	Consider the case where no two k2's match.
QED.

Actually, there are some sorting methods that are better than N log N;
use the best standard sorting algorithm you have.