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 worstcase 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 sameish 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. ↩︎