Cumulative Median in place of mean

Is there a way to find a cumulative median of an array without using a loop? I know of the cummean function on the file exchange, but in my application a median would be more appropriate than a mean. Thanks!

Answer 1

[Walter Roberson]

No, it is not possible. Every element must be examined at least once, in a non-trivial way. That is going to require a loop, or at least an implied loop (e.g., arrayfun).

The better question is whether it can be done efficiently or whether each median() request is essentially independent of each other. It is obvious that the efficiency can be improved by keeping a sorted vector of everything that has been input before and then adding each new element into its right place (an insertion which can be done in log time) and indexing the middle of the new vector. Improvements to that idea exist; see for example http://www.stat.cmu.edu/~ryantibs/papers/median.pdf