According to cppreference.com, the complexity of the C++ STL sorting algorithms is:
sort: O(N log(N))
partial_sort: "approximately" O(N log(M)), where M is distance(middle-first)
nth_element: "on average" O(N)
However, this seems to imply that, instead of doing a partial_sort, you could use nth_element and then sort the first range, to give an overall complexity of O(N + M log(M)), which is a bit better than O(N log(M)). Is this actually true? Am I better off avoiding partial_sort?
After extensive testing, it seems that partial_sort is faster for my use-case. I suspected as much -- but this seems to confirm it.