Fast new algorithm for finding 1D medians, implemented in Rust
(Do not use, not ready yet, apart from the naive_median)
Finding the medians is a common task in statistics and data analysis.
We argue in rstats that using the Geometric Median is the most stable way to charactarise multidimensional data. There, we solved the problem of finding it efficiently in n dimensions by implementing a stable algorithm with good convergence (an improved Weiszfeld algorithm).
That leaves the one dimensional case, where the medians are not used nearly enough, due to being slower to find than the arithmetic mean.
The median can be found simply by sorting the list of data and then picking the midpoint. The only problem with this approach is that, even when using a good quality sort with guaranteed performance, such as the Merge Sort, the complexity is O(n log n). The quest for faster algorithms is motivated by the simple observation, that not all items need to be fully sorted.
It is possible to approach O(n). This is the main claim of what is currently considered to be the best algorithm: Floyd-Rivest and 'Median of Medians'. Here we compete against this algorithm and run some comparisons.