Fast computation of rank order statistics

This paper proposes an algorithm for the computation of ID rank order statistics. For a window filter of size n and a rank r, the computation takes place on groups of 2n samples. Two ordered strings of r samples are constructed by straight insertion and their partial results are combined to cover n + 1 consecutive window positions. The filter output is found either directly taking the r-th sample in rank from ordered sequences (2 results) or by selecting it from two ordered sub-strings (n — 1) results. For ranks far apart from the median, the behavior of the algorithm is outstanding. Thus, for max/min the computational complexity, regardless the window size, is less than 3 comparisons/sample. For the second in rank, one gets less than 7 comparisons/sample, etc. When the rank approches the median, the computational complexity increases to O(log2 n).