# -*- org -*-

#+CATEGORY: sort

* Routines for selecting the k largest or smallest values could use

heapsort for speed O(N log k) rather than insertion O(N k).

* Sorting of complex arrarys without using additional memory. We try

to avoid allocating memory internally in GSL, so internally computing

the magnitudes and storing them in a temporary array is undesirable. 

Obviously a complex array can be sorted using sqrt(x*x + y*y) <=>

sqrt(u*u + v*v) (written in a numerically stable way) for every

comparison, but this may be unacceptably slow. Maybe not? It is just a

constant factor. The square roots could sometimes be avoided by

optimization,

    (x,y) = (MAX(|x|,|y|), MIN(|x|,|y|))

    (u,v) = (MAX(|u|,|v|), MIN(|u|,|v|))

    if (x < u/sqrt(2))     /* This part is optional optimization */

       return -1 

    if (x > u*sqrt(2))

       return +1

    if (x == 0 && u == 0) ...

    if (x == 0) ...

    if (u == 0) ...    

    t = u*sqrt((1+(v/u)^2)/(1+(y/x)^2))

    if (x < t)

       return -1

    if (x > t)

       return +1 

    else

       return 0

but this does depend on the data having sufficient range for the

optimization to be worthwhile, otherwise it is an extra cost.