Path: utzoo!attcan!uunet!zaphod.mps.ohio-state.edu!think.com!yale!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!sci.kun.nl!cs.kun.nl!hansm
From: hansm@cs.kun.nl (Hans Mulder)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Summary: you agree
Keywords: linear sorting, bytes, records
Message-ID: <2432@wn1.sci.kun.nl>
Date: 12 Nov 90 13:19:58 GMT
References: <5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <16709:Nov1113:56:2390@kramden.acf.nyu.edu> <237@smds.UUCP>
Sender: root@sci.kun.nl
Organization: University of Nijmegen, The Netherlands
Lines: 19



In article <237@smds.UUCP> rh@smds.UUCP (Richard Harter) writes:
> .....  I'll continue to
> sort n-byte files in time between bn and cn seconds for nonzero b and c.

In article <16709:Nov1113:56:2390@kramden.acf.nyu.edu>,
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) argues that if the file
contains N records, they must be at least log(N) long, in order to be
distinct, and that it takes at least N*log(N) time to sort them.

This is perfectly consistent: if there are N records and each is log(N)
bytes long, then there are N*log(N) bytes of data in the file.

In other words, n == N*log(N).  You agree.

Have a nice day,

Hans Mulder	hansm@cs.kun.nl