1

Currently the minima and maxima functions use @soroush's algorithm, which has expected running time of O(k log k + nk), where n is the number of elements in the sequence and k is the number of elements in the output.

Could these functions be improved with the median of medians selection algorithm[1]? It has worst-case running time of O(k log k + n) for sorted result, and O(n) for unsorted result. In addition to the lower time complexity, the same-ish algorithm can be used for finding the rank of elements.

Although, one significant disadvantage of the algorithm is that although it's O(n), it has a large constant, which makes it less useful for short sequences. Maybe it can replace sorting the entire sequence as the fallback for large n and k?

  1. Some references about the median of medians selection algorithm: the Wikipedia article, the paper that introduced it, and Introduction to Algorithms 3rd edition chapter 9.3. ↩︎

2

Cpp doesn't use MoM but a version of introselect. Under the std::nth_element algorithm std::nth_element - cppreference.com

+1 for adding that algorithm though. Super helpful!