Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.misc
Subject: Re: Lying
Message-ID: <4372@goanna.cs.rmit.oz.au>
Date: 26 Nov 90 09:24:51 GMT
References: <6097@lanl.gov> <4298@goanna.cs.rmit.oz.au> <246@smds.UUCP>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 13

In article <246@smds.UUCP>, rh@smds.UUCP (Richard Harter) writes:
> It should also be noted that bucket sorts, distribution sorts, math sorts,
> et. al. are linear only within a range.  [If the file size is large enough
> the implicit assumptions about short data access times fail.]

This applies to *all* "in-core" sorting methods.  It's not that the sorting
method breaks down, but that the "array access is constant time" assumption
breaks down.  That also applies to things like matrix multiplication!
One can use samples (as one does in linear-time selection algorithms) to
partition the collection into manageable pieces.

-- 
I am not now and never have been a member of Mensa.		-- Ariadne.