Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!dali.cs.montana.edu!ogicse!unmvax!uokmax!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <4297@goanna.cs.rmit.oz.au>
Date: 16 Nov 90 07:51:22 GMT
References: <8420:Nov1522:11:2290@kramden.acf.nyu.edu> <6082@lanl.gov>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 33

In article <6082@lanl.gov>, jlg@lanl.gov (Jim Giles) writes:
> Do they? Or do they also follow the convention that I claim is the
> universal: to quote speeds as a function of the number of _keys_ and
> (maybe) also in other terms - but _only_ after _explicitly_ stating
> what those other terms are?

I think that it is worth noting that quoting sorting speed as a function
of the number of bytes to be sorted is not an *arbitrary* criterion;
when we talk about an algorithm being O(f(N)) the argument N is usually
understood as measure of the size of the input, such as the number of
bits in a "reasonable" encoding.  [See for example Garey & Johnson.]

So the convention Dan Bernstein uses to describe MSD radix sort
(linear in the size of the input) is the convention which is usual
*except* for sorting.

How come sorting uses a different convention?  For the simple reason
that most discussions of sorting complexity consider keys as single
symbols.  A typical example is Sedgewick's Acta Informatica article
about quicksort, where the bottom line (that quicksort is quick) was
obtained by plugging into his formulas the assumption that the cost
of comparing a whole key is 1/4 of the cost of an integer assignment.

If we don't assume small keys, then since quicksort does O(K log K) key
(or pointer) moves on the average, K being the number of keys, and since
K distinct keys (or pointers) need O(log K) bits each, the average cost
of quicksort is O(K (log K)**2).

What was the Tarjan et al 1987 article again?  I think it's time I read it.

-- 
The problem about real life is that moving one's knight to QB3
may always be replied to with a lob across the net.  --Alasdair Macintyre.