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

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

david nicol
July 8, 2004 18:03
Re: optimizing Short circuiting sort method based on [M]
Message ID:
On Wed, 2004-06-30 at 08:11, Ton Hospel wrote:
> 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.

Does not the combining involve more comparisons?

david nicol
this message was sent from a filtering e-mail address.
Until I add you to my friends list, to get by Big Emet
the cowboy doorman your reply must include a listed
"magic phrase" such as "cat and buttered toast" Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About