In the first example of problematic calls to nth_element, there is another bug: if the container contains nothing, it will call nth_element with begin(), begin() - 1, ...
Also, typo: "compare functions much comply" -> "compare functions must comply"
> Fixes are trivial, access the nth element only after the call being made. Be careful.
Wouldn't the proper fix to do the nth_element for the larget element first (for those cases that don't do that already) and then adjust the end to be the begin + larger_n for the second nth_element call? Otherwise the second call will check [begin + larger_n, end) again for no reason at all.
Also, typo: "compare functions much comply" -> "compare functions must comply"