From: posting@sci.math
Subject: Re: Expected Performance of Heapsort
Date: Tue, 17 Aug 1999 03:39:45 GMT
Newsgroups: sci.math
From "Willse" :
> Scott-
>
> > Can anyone give the average runtime performance for Heapsort? I know
> > the worst case is 2*n*lg(n) + O(n), but I need the average case.
The attraction of heapsort is that the average run time is about the same as the worst
run time (which is supposedly about the same as the best run time) which is about N lg
N.
According to Knuth, 2nd ed, v 3, p 382, in theory heapsort average run time is 23.08 N
ln N + 0.01 N and maximum is 24.5 N ln N with the caveat that "average time is based on
an empirical estimate, since the theory is incomplete".
In practice, howerver, heapsort is about five-times slower than distribution counting
for N=1000 (with multiple list insertion and radix list sort not far behind at over
fout-times faster).