[comp.theory] A simple query on Heapsort

victor@WATSON.IBM.COM (Richard J Botting) (03/28/91)

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.