Article View: comp.lang.misc
Article #2023Re: A very brief history of optimal sorting methods
From: Hans Mulder
Date: Mon, 12 Nov 1990 13:19
Date: Mon, 12 Nov 1990 13:19
19 lines
1298 bytes
1298 bytes
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
Technical Details
Message-ID:
<2432@wn1.sci.kun.nl>Path:
arc1-ca.pugleaf.net!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!hansmReferences:
<5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <16709:Nov1113:56:2390@kramden.acf.nyu.edu> <237@smds.UUCP>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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