Re: stable sorts

[Daniel J Sebald]

On 08/25/2012 11:07 PM, Ed Meyer wrote:
> On Sat, Aug 25, 2012 at 7:40 PM, Michael D Godfrey
> <address@hidden <mailto:address@hidden>> wrote:
>
>     On 08/25/2012 09:55 PM, Ed Meyer wrote:
> >     Just because it has kept the order of x(2) and x(3) does not
> >     necessarily mean it is a stable sort;
> >     an unstable sort can do either but a stable sort is guaranteed to
> >     keep the original order.
> >
> >     --
> >     Ed Meyer
>     Yes.  But, this thread started from an error on my part.  I had thought
>     that Ben's fix for interp1 was based on the Octave sort not being
>     stable.
>     The real problem was with the direction of the discontinuity mechanism
>     in interp1.
>
>     I am pretty sure that Octave sort is stable, but this could be checked
>     more, of course.
>
>     Michael
>
>
> Comments in the code indicate it is a stable search;  the function is
> called binarysort but I've never heard of a binary sort so I'm not sure
> what it's doing :-(
> I think I'll run a bunch of tests to see if it ever does an unstable sort.

It's stable since the only data movement ever done is to shift blocks of 
elements outward.  I tested a small change to the block slide technique 
last night for a 5% to 7% reduction in CPU consumption.  Also, the 
associated file has some code duplication that could be fixed using C++ 
principles.  These aren't worth a change in the repository.

Dan