I seem to have found a bug in heapsort. When I enter the following array

0,0,0,0,20,0,28,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1

I get the following result:

0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,20,28

which is obviously wrong. I'm using the code for C, though I've translated it to Java. I know of one bug in the published code (the line "j = l+1" should be "j = 2*l+1"), which I have fixed, but I still get the above problem.

If I delete any of the zeros then the array gets sorted correctly. I can't figure out what the problem is. Any ideas? Is this just an inappropriate method when sorting arrays with so many zeros?

Thanks,
Karen

The bug you referred to was in v 2.10 of C++, not in the C code. (note that arrays in the C code are one-based, not zero-based as in C++). The array you gave sorts fine with hpsort.c.

Saul Teukolsky