k vs k-th in sort.texi

[James Theiler]

On Sun, 2 Mar 2003, Brian Gough wrote:

] Thanks for the doc patch, now applied.

Thanks Brian, for your untiring efforts.

] I think you are right about
] needing workspace (or destroying the input array) to get the k-th
] largest.

By an odd coincidence, I stumbled across a related function
in the STL.  It is called the nth_element, and it claims to
be O(N) where N is the size of the full array.  It is a
kind of partial sort of the array.  if A[] is the array,
and n=6, then after the partial sort, one has that
   A[6] has the value that it would have with a full sort
   A[0],...,A[5] are all <= A[6], but it is not necessarily
      the case that A[0]...A[5] are sorted among themselves
   and A[6] <= A[7],...A[N-1]

This is not quite the same as our gsl_sort_smallest, which would put
the six smallest elements into a separate sorted list.  STL provides
another function, called partial_sort, which is a lot more like
what the GSL provides.

I am of the school that says you shouldn't implement something unless
you need it, but this does seem like a nifty function for the GSL to
provide.  More details in Austern's book, Generic Programming and the
STL, Addison-Wesley, 1999, Section 13.1.5.

jt

---------------------------------------------
James Theiler                     jt@lanl.gov
MS-D436, NIS-2, LANL        tel: 505/665-5682
Los Alamos, NM 87545        fax: 505/665-4414
----- Space and Remote Sensing Sciences -----