CareerCup

1) use quicksorts partition method to split into half, this will separate your array into elements: < median and >= median
2) on the upper half of this array, use the same partition method to separate on kth position, you will then have an array of median ... median + k in O(n) time
3) this array you need to sort which will lead to the O(n + k * log(k))

things to consider:
- median is ambigious as there exists a median element if the array is of odd size, if of even size, there is an floor-median and a ceiling median and in statistics the real median is the average of them, here either the floor or ceiling is ment I suppose.
- the partition method has a few properties that are not so nice if implemented in a primitive way and applied for example on a sorted array or an array with all the same elements in it. Randomization is an approach, and split into three parts < = > is an alternative

@Ankita: some pivot will divide into half, most often not the first of course, see partitionAroundKth:

int partition(int *array, int first, int last)
{
// typical partition code
// returns arbitrary index in the range [first, last] which is the
// index of the pivot
}

void partitionAroundKth(int *array, int first, int last, int k)
{
int pi = -1;
while(pi != k)
{
pi = partition(array, first, last);
if(pi > k) last = pi - 1;
if(pi < k) first = pi + 1;
}
}

@ChrisK
Thanks for reply!
But what if the data has random numbers, and the pivot I select does not divide into half?Is there any specific way in selecting pivot?
Generally I prefer using last element as pivot