develooper Front page | perl.perl5.porters | Postings from June 2004

Re: optimizing Short circuiting sort method based on [M]

From:
perl5-porters
Date:
June 30, 2004 06:12
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
cbue55$su2$2@post.home.lunix
In article <40E2774F.1070106@perltraining.com.au>,
	Paul Fenwick <pjf@perltraining.com.au> writes:
> I haven't thought about any other sorting algorithms yet.  I agree that 
> heapsort is definitely worth examining as an efficient way to gathering 
> only the first sorted M elements, as at each stage the next element is 
> known (the root), and there are only two choices for the next element 
> (the immediate children of the root).
> 

Mergesort works well too if you cut off runs at M.
you start with N/M groups of M elements, each sort in O(MlogM), so that
gives (NlogM).
Then you need to combine N/M runs, which is (N/M-1) combines, in which each
can stop after collecting M elements => O(N).
So the sum is still O(NlogM)

And since the plain sort already is mergesort, i think that would be 
the best choice since it will e.g. have the same stability properties,
and the partial sort smoothly extends to the full sort.



nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About