Keep a small heap for the largest k values

For the k largest values, keep a min-heap of at most k items. After each insertion, remove the smallest if the heap grows past k. At the end, the root is the kth largest, assuming there are at least k values. The heap uses O(k) space and takes O(n log k) time when k is at least 2, or O(n) when k is 1. Sort the retained items separately if sorted output is needed.