Re: a question about gsl_sort_***

Re: a question about gsl_sort_***

[Brian Gough]

Arin Chaudhuri writes:
 > Dr. Gough,
 > I don't know much about design issues but I was wondering about
 > the reason behind the choice of algorithm gsl_sort_smallest. I was
 > wondering about this simple alternative:
 > We build a heap then we simply pull out the k largest elements. The most
 > efficient method of building a heap is O(N) pulling out k
 > elements from the heap require a further klog(N) steps, but of course
 > for this we will have to make a copy of the original array. Unless the
 > cost of duplicating a large array makes up for the decrease in complexity
 > from kN to cN+klog(N) we should be fine, or am I missing something?
 > regards,
 > Arin

I wanted an algorithm that did not use any extra memory and preserved
the original array.  It is possible to use a heap for the k elements,
which increases the efficiency for large k, but I implemented the
easier option of direct insertion since large k is not often used in
practice. See Knuth vol 3 for all relevant details.

-- 
Brian