Counting big enough elements
You can do it in linear time, using an efficient selection algorithm.

Find the median, and partition the array into numbers below the median and numbers above the median.  Check whether the number you're looking for is above or below the median.  Then, recurse on the appropriate partition.

The running time satisfies the recurrence $T(n)=T(n/2)+O(n)$, since you can find the median and partition the array in $O(n)$ time.  The solution to this recurrence is $T(n)=O(n)$, so the total running time is $O(n)$.  This is faster than your $O(n \log n)$ time algorithm.