[smiths1999]

They are probably thinking of simply going through the list and tracking the top 3. This gives you linear time but as you noted you can go faster with quickselect (edit: I originally mistakenly wrote selection sort despite thinking of quickselect), giving you linear time (edit: I original said logarithmic time, which is obviously wrong).

I suppose it is besides the point, but you shouldn't be reaching for a specific algorithm but rather using your language's library sort algorithm.

[andi999]

What do you nean with selection sort giving logarithmic time? I mean any algorithm finding anything unique on an unsorted list has to be at least O(n) or resort to magic.

[smiths1999]

Well I was actually thinking of quickselect, but regardless I was too quick to post. Quickselect is O(n) average time (as you pointed out).