Front page | perl.perl5.porters |
Postings from July 2004
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"