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