Many big data analysis companies like Palantir love this interview problem as its' part of their daily job.|
Selection sort (a.k.a. Quick Select) can be better! It is mostly used in real-time streaming data analysis compares to the external sort which requires access to hard drive (memory latency is smaller than hard drive).
In worst case, quick select could be O(n + klogk), however, if we only need to find top k most, the O(klogk) part can be eliminated, which leaves an O(n) only.