6 Jul
2009
6 Jul
'09
7:32 p.m.
It seems to me, that you just need a selection algorithm which works in O(n * k) time for k arbitrary elements. If you combine O(n*k) selection algorithm with any O(n * lg n) sort, you furfil your time constrain.
I guess, we also want the list to be sorted in O(1) after having selected every element. Matthias.