Guys , for this question, i have been able to come up with the
O(n logn) - by sorting, and
O(n.k) - by Tournament Principle algorithms,

I read in a few places about Ordered Statistics but couldnt get anything out of it.
Please can some1 give me an O(n) algo ????

I have a Microsoft Interview tomorrow :)

Just want to make it clear that i m looking for kth largest in a single array, and not in the union of 2 sorted arrays..

I would use moving maximums to k array or keeping sorted k length array built from the long array. Or I would adapt quicksort to take pivots from correct side.

priority queue with some adaptation , but O(n) is quite hard

Keeping a sorted list/tree of k values would be O(n log k), I think.

If someone asserts that k is a constant, making this O(n), then I'll assert that for any given run, n is a constant, so it's really O(1). ;->