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

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

From:
perl5-porters
Date:
July 9, 2004 07:21
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
ccm9if$ufs$1@post.home.lunix
In article <1089335013.1041.182.camel@plaza.davidnicol.com>,
	david nicol <davidnicol@pay2send.com> writes:
> Does not the combining involve more comparisons?

Sure, but I accounted for them. N/M combines each collecting M elements
from 2 runs of M => M compares per combine => O(N) compares, which then
gets subsumed in the O(N log M) we already had from the first step



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