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

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

From:
david nicol
Date:
July 8, 2004 18:03
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
1089335013.1041.182.camel@plaza.davidnicol.com
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" 




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