Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site spuxll.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!spuxll!ech
From: ech@spuxll.UUCP (Ned Horvath)
Newsgroups: net.math
Subject: Re: Sorting a sorted list by a different order of keys
Message-ID: <668@spuxll.UUCP>
Date: Wed, 12-Jun-85 17:37:06 EDT
Article-I.D.: spuxll.668
Posted: Wed Jun 12 17:37:06 1985
Date-Received: Fri, 14-Jun-85 00:45:32 EDT
References: <7298@watdaisy.UUCP>
Organization: AT&T Information Systems, South Plainfield NJ
Lines: 23

Example of faster than nlogn sort: the keys are precisely the integers
1..n.  In other words, each key tells you what directly what cell of the
sorted array it belongs in.  The following pseudo-C then does the sort:

	for (i = 0; i < n; i++) {
		while (key[i] != i) {
			exchange (i, key[i]);
		}
	}

Note that every exchange puts (at least) one element in its final position,
so clearly the number of exchanges is upper-bounded by n-1.  Similarly
the while test can succeed at most n-1 times and fail at most n times
(total), so the whole thing is linear.

This sounds like a cheat, but indeed many 'real world' sorting problems
are of this type.  Another classical example is creating a new phone book:
I have a (very large) already sorted file -- the old phone book -- along
with a fairly short list of additions and deletions.  As a function of the
total size of the result, sorting the changes and merging is effectively
linear.

=Ned=