On smaller window sizes,
n log n sorting might work. Are there any better algorithms to achieve this?
#Edit: As @Hunaphu's points out (and @whuber below in his answer) the original answer I gave to the OP (below) is wrong. It is indeed quicker to first sort the initial batch and then keep updating the median up or down (depending on whether a new data points falls to the left or to the right of the current median).
It's bad form to sort an array to compute a median. Medians (and other quantiles) are typically computed using the quickselect algorithm, with $O(n)$ complexity.
You may also want to look at my answer to a recent related question here.
If you're willing to tolerate an approximation, there are other methods. For example, one approximation is a value whose rank is within some (user specified) distance from the true median. For example, the median has (normalized) rank 0.5, and if you specify an error term of 10%, you'd want an answer that has rank between 0.45 and 0.55.
If such an answer is appropriate, then there are many solutions that can work on sliding windows of data. The basic idea is to maintain a sample of the data of a certain size (roughly 1/error term) and compute the median on this sample. It can be shown that with high probability, regardless of the nature of the input, the resulting median satisfies the properties I mentioned above.
Thus, the main question is how to maintain a running sample of the data of a certain size, and there are many approaches for that, including the technique known as reservoir sampling. For example, this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136
Here is an article describing one possible algorithm. Source code included and a quite serious application (gravitational wave detection based on laser interferometry), so you can expect it to be well tested.
If you maintain a length-k window of data as a sorted doubly linked list then, by means of a binary search (to insert each new element as it gets shifted into the window) and a circular array of pointers (to immediately locate elements that need to be deleted), each shift of the window requires O(log(k)) effort for inserting one element, only O(1) effort for deleting the element shifted out of the window, and only O(1) effort to find the median (because every time one element is inserted or deleted into the list you can update a pointer to the median in O(1) time). The total effort for processing an array of length N therefore is O((n-k)log(k)) <= O(n log(k)). This is better than any of the other methods proposed so far and it is not an approximation, it is exact.
Here is a solution O(1) for finding current median, and O(log n) for adding a new number http://www.dsalgo.com/RunningMedian.php
As you mentioned sorting would be
O(n·log n) for a window of length
n. Doing this moving adds another
l=vectorlength making the total cost
The simplest way to push this is by keeping an ordered list of the last n elements in memory when moving from one window to the next one. As removing/inserting one element from/into an ordered list are both
O(n) this would result in costs of
l = length(input) aidvector = sort(input(1:n)) output(i) = aid(n/2) for i = n+1:l remove input(i-n) from aidvector sort aid(n) into aidvector output(i) = aid(n/2)
If you can live with an estimate instead of the true median, the Remedian Algorithm (PDF) is one-pass with low storage requirements and well defined accuracy.
The remedian with base b proceeds by computing medians of groups of b observations, and then medians of these medians, until only a single estimate remains. This method merely needs k arrays of size b (where n = b^k)...
I used this RunningStats C++ Library in an embedded application. It is the most simple running stats library I have found yet.
From the link:
The code is an extension of the method of Knuth and Welford for computing standard deviation in one pass through the data. It computes skewness and kurtosis as well with a similar interface. In addition to only requiring one pass through the data, the algorithm is numerically stable and accurate.