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).