Re: More Informed Sort

[David Bateman]

> Unfortunately, the C++ below doesn't make much sense to me.  After looking 
> at the wikipedia page on mergesort 
> (http://en.wikipedia.org/wiki/Merge_sort), I came to the conclusion that 
> I'm looking for direct access to the merge functionality of mergesort.  Is 
> that what your code below says?


Yes, you have direct access to the merge functionality of the merge 
sort. The code identifies the partially sorted lists. Consider

octave:1> t0 = 0; for i = 1:10, t=cputime(); sort(randn(1e6,1)); t0 = 
t0+cputime()-t; endfor; t0/10
ans = 0.61681

against

octave:2> sorted=sort(randn(1e6,1));t0 = 0;for i = 1:10; x = 
[randn(1e4,1); sorted]; t=cputime(); sort(x); t0=t0+cputime()-t; endfor; 
t0/10
ans = 0.094186

and then

octave:3> partiallysorted=[sort(randn(1e6,1));sort(randn(1e4,1))];t0 = 
0;for i = 1:10, t=cputime(); sort(partiallysorted); t0=t0+cputime()-t; 
endfor; t0/10
ans = 0.091286

and finally

octave:4> sorted=sort(randn(1e6,1));t0 = 0;for i = 1:10, t=cputime(); 
sort(sorted); t0=t0+cputime()-t; endfor; t0/10
ans = 0.073989

and even furthermore consider

octave:5> 
partiallysorted=[sort(randn(1e6,1));flipud(sort(randn(1e4,1)))];t0 = 
0;for i = 1:10, t=cputime(); sort(partiallysorted); t0=t0+cputime()-t; 
endfor; t0/10
ans = 0.090986

so octave doesn't even care if the partially sorted lists are in reverse 
order...

D.

--
David Bateman                                address@hidden
Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob) 
91193 Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax) 

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------