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?

Regarding reference implementation, now I find definition of median finding in both median.scm and select.scm (I was looking the former, which just calls vector-sort). It appears median.scm isn't referenced anymore, so maybe it should be deleted.

On Tue, Jan 24, 2017 at 4:13 PM, Alex Shinn <xxxxxx@gmail.com> wrote:

On Wed, Jan 25, 2017 at 10:29 AM, Shiro Kawai <xxxxxx@gmail.com> wrote:
The current srfi says vector-find-median runs in O(n), whilest vector-find-median!
runs in O(n ln n). Shouldn't the former be O(n ln n) as well? The reference
implementation looks like it is O(n ln n), and I don't see how to make it run in O(n).

Median is a special case of vector-select, which runs in linear time.

The SRFI implies that vector-find-median! (fully) sorts the vector,
meaning the partial sort of vector-separate! can't be used. If this
is the correct interpretation, then it must be O(n log n), slower than
the non-mutating version.

--
Alex