With the addition of a correct median for even nr elements, this lib is more or less done.

There are still some ideas to investigate, mainly if and when a complete sort is needed.

1) GetMedian() does not need a complete sort(). Sorting only half+1 is enough to detemine the median. There exists QuickMedian algorithm (from Hoare, inventor of quicksort) which recursively selects the partition in which the median lies. It is O(

^{2}Log n) on average. Worst case it does a complete sort O(n

^{2}). It probably means an increase in code size.

2) getHighest() and getLowest() can be found with one iteration over the array O(n) similar to getAverage(). However a sorted array gives the lowest and highest in O(1).

3) getAverage(nMedians) needs a complete sort, or at least a partial sort which encloses the nMedians. A partial quicksort that only sort those partitions that include the range nMedians could do some good. Added complexity is probably the price.

4) Keeping the elements sorted after single addition/replace is optimal with insertSort() - see my modifications of the FastRunningMedian(rkail) above. Merging the speed of FastRunningMedian with functionality of RunningMedian is the holy grail

New function ideas:

Quartile(n),n=0,1,2,3,4 where the median is the 'half' element, quartile(0) = lowest(), quartile(1) is element at quart, quartile(2) == median, quartile(3) is element at 3/4 and quartile(5) is highest.

getElement(n) + getSortedElement(n) readonly access to the (sorted) internal buffers. would make implementation of quartile, lowest and highest trivial, and allows iteration to do whatever the user wants.

mode() returns the element that occurs most often. Problem is that this is not always one unique number e.g. all numbers occur once.

predict()returns the largest distance to the neighbour of the median. e.g.

{1,2,3,4,5}-> median = 3 predict()= 1

{1,2,3,4,7,9,10,11} median=7, predict()=3

It predicts the maximum change the RunningMedian will make after an addition. e.g. If predict()= 0 means that the RunningMedian will stay the same (stable). Could be parametrized (d distance) d = [1..cnt/2]. There is complexity in the code when the internal buffer is not filled yet, unless this is pre-filled like in FastRunningMedian. Also even/odd adds extra code.

For me the getElements, getSortedElements are the most interesting. Followed by the predict(d). Enough to tinker