Re: stable sorts

[Ben Abbott]

On Aug 25, 2012, at 2:44 PM, Michael D Godfrey wrote:

> Ben,
> 
> I checked a few things about sorts:
> 
> 1. The term for a sort which correctly orders the indices of
>     equal objects is "stable."
> 
> 2. Our current Matlab (2009b) implements unstable sort,
>     matching Octave.  But there is the following Note
>     in the Mathworks Newsletters (dated 2004):
>    
> http://www.mathworks.com/company/newsletters/news_notes/dec04/adventure.html
>    This says a number of interesting things, but they do not match the
>    version of Matlab that we use.   However, our matlab does have sortrows,
>   which is claimed to be based on a stable sort. 
> 
> Octave sortrows says in the code:
> 
>   ## Since sort is 'stable' the order of identical elements will be
>   ## preserved, so by traversing the sort indices in reverse order we
>   ## will make sure that identical elements in index i are subsorted by
>   ## index j.
> 
> This documentation is ambiguous, at least to me, but it looks like the
> code does the right re-ordering.  But, I have not run a test case.
> (I take the first line of the comment above to mean "Since sortrows is 
> stable..."
> 
> An important point would be to find out if newer Matlabs implement sort
> as stable.  If they do, there is a strong compatibility argument for updating
> Octave sort.  However, I think that it may be a good idea to make sort stable
> in any case.  There is some feeling that, despite many unstable sorts, 
> including
> C qsort, unstable is actually incorrect.  I agree with this.  I think that 
> the latest
> interp1 (with your fix) will still work with a stable sort.  Is this correct?
> 
> Finally, the Mathworks newsletter talks about visort, vqsort, and vrsort, but 
> our
> 2009b matlab does not provide these.  If they are in newer  matlabs, it would
> be good to implement them.
> 
> Michael

Michael,

I'm not sure I'm understanding this, but if you can provide an example, I'll 
try it out using the most recent Matlab release.

Ben