Sorting Algorithm 2

Question

An in-place algorithm with O(n) running time that rearranges an unsorted array A[0 . . . n − 1] filled with distinct integers so that, for a given k (1<=k<=n), A[0 . . . k − 1] contains the k smallest integers in increasing order.

Is there an existing algorithm that meets these specifications, or one that can be altered to meet them, I appreciated the quick response to my earlier question.

Thanks

Answer 1

If you google for O(n) sorts, you would end up with Counting Sort or Radix Sort.