On Thu, Sep 28, 2006 at 11:18:45PM +0800, keios wrote:-
> It is a non-standard heap-sort algorithm implementation because the
> index of child node is wrong . The sort function still outputs right
> result, but the performance is O( n * ( log(n) + 1 ) ) , about 10% ~
> 20% worse than standard algorithm .
> Signed-off-by: keios <keios.cn@xxxxxxxxx>
Was a bit mystified by this as your patch matches what I've got
in my userspace test harness from 2003.
Here's what I submitted, which is almost the same as yours:
Then Zou Nan hai sent Andrew a fix for an off-by-one bug here (merged
with my patch):
..which introduced the performance regression.
And then I subsequently tweaked my local copy for use in another
project, coming up with your version.
So this passes my test harness just fine (for both even and odd array
Acked-by: Matt Mackall <mpm@xxxxxxxxxxx>
Mathematics is the supreme nostalgia of our time.