From octave-maintainers-request at bevo dot che dot wisc dot edu Mon Jan 19 09:14:23 2004
Subject: Re: benchmarks - sort
From: Paul Kienzle <pkienzle at users dot sourceforge dot net>
To: David Bateman <David dot Bateman at motorola dot com>
Cc: octave-maintainers at bevo dot che dot wisc dot edu
Date: Mon, 19 Jan 2004 10:13:42 -0500

If you are going to implement it, keep compatibility
for complex sort, since any code that uses it is going
to depend on the order.

Complex sort could be used to match complex pairs.
Chances are, though, that it is not going to be very
reliable since the complex pairs may have differing
magnitudes due to machine precision issues.  Has
anyone actually seen complex sorts in the wild?

It is tempting to just punt on  complex sort and tell
the users to use the following instead:

	[junk,idx] = sortrows([abs(x(:)),arg(x(:))])
	y = x(idx);

That way they will know they are doing a meaningless
operation.

A couple of other points:

(1) Octave's existing sort is stable (i.e., equal values
retain their order).

(2) Make sure to check the case of a sorted or almost
sorted array.  These occur quite a bit in existing code
(e.g., lookup and hist).

Paul Kienzle
pkienzle at users dot sf dot net

BTW, the python folk are quite proud of their sort.  A description of  
the
algorithm is here:
http://cvs.sourceforge.net/viewcvs.py/python/python/dist/src/Objects/ 
listsort.txt?rev=1.1&content-type=text/vnd.viewcvs-markup

And the code is here:
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/python/dist/src/ 
Objects/listobject.c?rev=2.131&content-type=text/vnd.viewcvs-markup

(starting at "Lots of code for an adaptive, stable, natural mergesort"  
and going to
PyList_Sort).

On Jan 19, 2004, at 5:40 AM, David Bateman wrote:

>
> Now the question becomes one of how to treat the complex sorts. I
> could easily sort on the absolute values, but this doesn't respect the
> ordering of values with the same magnitude by there phase as matlab
> does. What I suspect Matlab does is to convert the complex values to
> magnitude and phase with the magnitude being more significant and then
> do a radix sort on this.  However, this will be much slower than the
> double sort, as I'll have to create 12 histograms and not 6 as at
> present, and I'll then have to make 12 passes through the data and not
> 6 to order the data correctly. Sorting only on the absolute value
> without respecting this phase condition should be only twice as slow
> as the double sort. This would explain why the sort of complex values
> is roughly 20 times slower on Matlab.
>
> Should I aim for exact Matlab compatiability in the sort algorithm, or
> "good enough" and lightning fast for the sorting of complex values. It
> should be noted that I don't think octave respects this sorting  
> condition
> at the moment in any case.