Find m smallest elements in an array of size n where m = n/2

So we have an unsorted array, we need to find the first $$m$$ elements in ascending order (or $$m$$ smallest elements) where $$m = \mathrm{array.size}/2$$ (or $$n/2$$). How would we do this in linear $$O(n)$$ time.

What I was thinking of doing was use the SELECT algorithm to find the kth smallest element until $$k = m$$, but this way the complexity would be $$n/2 \cdot O(n) = O(n^2)$$.

• You want to find the $m$ smallest numbers, and they have to be sorted? If yes, it is not possible to do so because it will give a $O(n)$ solution to sort the entire array and this violates the fact that comparison-based algorithm must sort in $\Omega(\log n)$ – Christopher Boo Mar 12 at 5:22
• @ChristopherBoo I think that “in ascending order” might explain what we mean by “first $m$ elements”. – Yuval Filmus Mar 12 at 9:15

Find the median in $$O(n)$$ time. Then go over the array and take out all elements smaller than the median.
You can create a min heap ($$O(n)$$) and then perform extract min m times. ($$O(mlogn)$$). Time complexity will be $$O(n) + O(nlogn)$$.
• While this does not answer How would we [find the $m$ smallest elements] in linear $O(n)$ time, it does present how to find the first $m$ elements in ascending order. – greybeard Mar 12 at 9:26