Find median of unsorted array in $O(n)$ time?

Question

To find the median of an unsorted array, we can make a min-heap in O(n log n) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(n log n)time.Can we do the same by some method in O(n) time? If we can, then how?

Answer 1

Sort them using QUICKSORT