You can use the median of medians k times in order of 0 to k. This will give you O(kn) runtime, this is probably the best solution. Another solution could be to sort and then take the k first elements which give O(nlogn) runtime.