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?
-
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. ↩︎