Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!WATSON.IBM.COM!victor
From: victor@WATSON.IBM.COM (Richard J Botting)
Newsgroups: comp.theory
Subject: A simple query on Heapsort
Message-ID: <9103271747.AA08417@irt.watson.ibm.com>
Date: 27 Mar 91 17:47:17 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Richard J Botting <victor%watson.ibm.com@VM1.NoDak.EDU>
Lines: 13

This is probably a question with a well known answer, but I am not
an expert on sorting algorithms...It is well known that the worst case
time to sort n items using Heapsort is O(n lg(n)) --where lg is log base 2.
Question: What kind of data gives this worst case?

Here is a more general question - Is anyone working on the analysis of
algorithms where the time to access data depends on its position on
a slow direct access store - eg. hard disk.  I've published some
results on searching and wonder if anyone has looked at sorting.

Richard J Botting
California State University, San Bernardino.
Dept. Computer Science.