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

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

From:
Paul Fenwick
Date:
June 30, 2004 07:56
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
40E2D47C.80909@perltraining.com.au
G'day Ton/P5P,

Ton Hospel wrote:

> Mergesort works well too if you cut off runs at M.

You're absolutely right.  Quicksort throws away unnecessary elements at 
the start (except in pathological cases).  Mergesort throws them away at 
the end (once runs start to become bigger than M).  Both of them become 
much faster by having M < N.

In the end, I would expect the complexity to be the same.

> 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.

I'm inclined to agree here.  If regular sort is simply a special case of 
truncated sort, then it avoids the unpalatable idea of having to 
maintain two separate sorts in Perl.  This is a good thing.

The question still remains as to what should happen when sort is called 
in a scalar context.  Does it return the smallest value, the sortedness 
value, or play nethack?  ;)

Cheers,

	Paul

-- 
Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/
Director of Training                   | Ph:  +61 3 9354 6001
Perl Training Australia                | Fax: +61 3 9354 2681



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