Oh, that solution can be quite efficient. You just have to generalize the problem in the right way. :-)

An example where the moral equivalent of your approach is efficient is if you want the top m elements out of a set of n. Make the sort be a lazy sort (eg heapsort) so that you only do the necessary comparisons. The efficiency is then O(n+m*log(n)), which is about as good as you will get.