Order statistics. in O(n) time. Kth largest element. if there are n element then we can find (n-1)th element in O(n) time

Do not use sorting. The complexity, at best, will be O(nlogn) and Space(n). Instead, scan the list with two values -- the highest and the second highest, comparing and swapping as you go. It may seem lo-tech, but algorithm complexity should be a concern, and this way is O(n) and Space(1) and is reliably the fastest way. Sorting the list is beneficial if you will be asking for an arbitrary n-th item often, or if the rank of the item you want is deeper than log(n) (i.e., find the 500th element in a list of a million elements). In my opinion, this question is about passing over an obvious solution for a better solution. Here is the pseudocode: Trivial case: The array is already sorted. Choose item[1] or item[n-1], depending on the sort order. Complexity is O(1) Normal case: (assume 0-index array 'items' of length n) Let h1 = list[0] Let h2 = list[1] loop from 1..n-1 if items[loop] > h1 then h2 = h1 h1 = items[loop] else if items[loo[ > h2 then h2 = items[loop] end if next return h2