htswanalysis/MACS/lib/gsl/gsl-1.11/sort/TODO

   1 * Routines for selecting the k largest or smallest values could use
   2 heapsort for speed O(N log k) rather than insertion O(N k).
   3
   4 * Sorting of complex arrarys without using additional memory. We try
   5 to avoid allocating memory internally in GSL, so internally computing
   6 the magnitudes and storing them in a temporary array is undesirable.
   7
   8 Obviously a complex array can be sorted using sqrt(x*x + y*y) <=>
   9 sqrt(u*u + v*v) (written in a numerically stable way) for every
  10 comparison, but this may be unacceptably slow. Maybe not? It is just a
  11 constant factor. The square roots could sometimes be avoided by
  12 optimization,
  13
  14     (x,y) = (MAX(|x|,|y|), MIN(|x|,|y|))
  15     (u,v) = (MAX(|u|,|v|), MIN(|u|,|v|))
  16
  17     if (x < u/sqrt(2))     /* This part is optional optimization */
  18        return -1
  19     if (x > u*sqrt(2))
  20        return +1
  21
  22     if (x == 0 && u == 0) ...
  23     if (x == 0) ...
  24     if (u == 0) ...
  25
  26     t = u*sqrt((1+(v/u)^2)/(1+(y/x)^2))
  27
  28     if (x < t)
  29        return -1
  30     if (x > t)
  31        return +1
  32     else
  33        return 0
  34
  35 but this does depend on the data having sufficient range for the
  36 optimization to be worthwhile, otherwise it is an extra cost.