I'm trying to implement an online running median filter. It is supposed to give out the median value from a list of 101 elements. When a new input is available, the oldest value is dumped, newest taken and median produced. Now, initially the sorting will be expensive but once the array is sorted computational load should decrease. I have two questions here:
1) What algorithm is best for sorted or mostly sorted array?
2) Since I need to remove the oldest value, I also need to store the index of the sorted array right? Is there a better way of doing thinks.
Any pointers would be much appreciated.
Many thanks.