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

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

June 30, 2004 06:12
Re: optimizing Short circuiting sort method based on [M]
Message ID:
In article <>,
	Paul Fenwick <> 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. Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About