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)$.
Find the median in $O(n)$ time. Then go over the array and take out all elements smaller than the median.