Partial sort

Exercise 4.10

The partial_sort algorithm of the C++ Standard Template Library takes a vector with n elements and a value m, with 1 \leq m \leq n, and re-sorts the vector in such a way that its first m elements are the lowest m elements of the original vector, in increasing order.

• Explain how to implement this function in a way that its cost in the worst case scenario is O (n + m \log n).
• How could it be implemented for its cost to be O(n \log m)?