On Wed, Jan 25, 2017 at 11:23 AM, Shiro Kawai <xxxxxx@gmail.com> wrote:

Yes, vector-select is O(n + k ln k), so if k is fixed, it's O(n). However, in median case k = n/2 and you can't fix k, can you?

vector-select is O(n), independent of k, as using the

algorithm I provided in selection.scm. See

A simple (untested) linear version of vector-find-median is then:

(define (vector-find-median < v knil . o)

(let ((len (vector-length v)))

(cond

((zero? len) knil)

((odd? len) (vector-select! < (vector-copy v) (+ 1 (quotient len 2))))

(else

(let ((mid (quotient len 2))

(v (vector-copy v))

(mean (if (pair? o) (car o) (lambda (a b) (/ (+ a b) 2)))))

(mean (vector-select! < v mid) (vector-select! < v (+ mid 1))))))))

Alex