Maintaining a sorted moving window I have an array of length $n$ representing a time series of data. I want to implement a moving (sliding) window of length $k &lt; n$ and calculate things like sliding median, sliding quantile, sliding trimmed mean, etc. Each of these requires the data to be sorted prior to calculating the statistic of interest.

Therefore I need a data structure which has the following 2 properties:


It must easily allow a new sample to be added and the oldest sample to be deleted as the window slides along the time series.
When a new sample is added, it should efficiently insert the sample into a sorted position in the data structure, so that things like the median and trimmed mean can easily be computed.


For #1, I am currently using a ring (circular) buffer of length $k$. This makes it easy to add new samples and overwrite old samples in $O(1)$ time simply by updating the head and tail pointers of the buffer.

For #2, I had thought to keep a separate array called perm to keep track of the permutation of the ring buffer entries needed to sort them. In other words, if array is the ring buffer array with head and tail pointers, then array[(head + perm[i]) % k] is the sorted array for i = 0,...,k-1. I tried using an Insertion Sort algorithm to update the perm array each time a new sample is added to the sliding window. The code for this is below.

/* sort ringbuf entries with insertion sort algorithm */
void
ringbuf_isort(const ringbuf *rbuf, int *perm)
{
  const int n = ringbuf_n(rbuf);
  int i, j;

  for (i = 1; i &lt; n; i++)
    {
      int id = perm[i];
      double v = rbuf-&gt;array[(rbuf-&gt;head + id) % rbuf-&gt;size];

      for (j = i; j &gt; 0; j--)
        {
          if (rbuf-&gt;array[(rbuf-&gt;head + perm[j-1]) % rbuf-&gt;size] &lt; v)
            break;

          perm[j] = perm[j-1];
        }

      perm[j] = id;
    }
}


This code works correctly and sorts the ring buffer entires, however it is far too slow. I have tracked the slowdown to the modular arithmetic (rbuf-&gt;head + id) % rbuf-&gt;size in each loop iteration. This can be moderately improved by doing a comparison of id &lt; head ? head + id : head + id - size, but this is still too slow.

In fact I have found it is faster to simply copy the ring buffer entries to a linear array and use a quicksort algorithm than using the above code.

Can anyone suggest a data structure which will solve the sorting problem and still be fast?
If you use augmented AVL (or any self-balancing tree like RB) tree with additional pointers for quantiles then maintaining median and quantiles work in logarithmic time. Inorder traversal is always sorted so if juggling with pointers is not good option for you, maintain tree, with one insert and delete per move and caclulated statistics during inorder traversal.

It is good to keep online algorithms whenever possible, keeping say mean or variance as accumulators, not recalculating all the time.

I have similar need, only maintaining median, mean, standard deviation and kurtosis. Here I keep threaded AVL tree with additional online version of statistics, moving median pointer on insert/delete.