stable sorts

[Michael D Godfrey]

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