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

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

Thread Previous | Thread Next
david nicol
July 8, 2004 19:51
Re: optimizing Short circuiting sort method based on [M]
Message ID:
On Thu, 2004-07-08 at 21:14, david nicol wrote:

> After finding runs, we can find the M best with M*R more comparisons.
> Which may or may not be an improvement over a NlogM single pass.  How
> big do the numbers have to be before it's worth the expected 1.5*N
> comparisons to find out how small R is, given that after determining R
> we can still fall back to the single pass when M*R is larger than NlogM?

while collecting runs we can give up on the whole deal when we have too
many runs.  Too many runs is :

	M*R > NlogM

        R > (NlogM)/M

so, calculate that, then collect runs, if we make it through the whole
array with fewer, shift elements off of runs, otherwise do a single
pass with binary insertions.

I'm sure everyone is sick of me posting less-than-fully-baked postings
by now, I thank you for your continuing indulgence.

david nicol
"cat and buttered toast" 

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About