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

https://en.wikipedia.org/wiki/Selection_algorithm.

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