sort index ordering

[John W. Eaton]

On  7-May-2000, Paul Kienzle <address@hidden> wrote:

| Hi! Does anyone know if sort is guaranteed to preserve relative index
| order for identical sort values? 
| 
| E.g.,
| 
|       octave> [s,idx]=sort([1,2,3,1])
|       s =
| 
|         1  1  2  3
| 
|       idx =
| 
|         1  4  2  3
| 
|       ^^^^^^^
| 
| The values in idx are increasing when the values in s are the same.  It
| is true for the cases I've checked, but I want to be sure that it is
| true in all cases, and that this characteristic will be preserved even
| if the sort algorithm is changed.

Yes, I want Octave's sort algorithm to be stable, which is why Octave
uses algorithm 5.2.4L from Knuth, Volume 3 (noted in the comments for
sort.cc) instead of something quick and simple like qsort from the C
library, which is not guaranteed to be stable.

I'm not sure if Matlab guarantees that its sort algorithm is stable,
but I believe that it appeared to be when I checked (several years ago
now).

jwe



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

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