Although
partial_sort is usually faster than a full
sort because it has to do less work, if you are going to be sorting most (or all) of the range, it can be slower than a full
sort .