Quick sort is one of the well known generic sorting algorithm in practice. It is popular since it is average running time is O(nlogn) << O(n²), and most of the time, it generates the results in a quick time.

As you read from your textbook, running time of Quick sort strictly depends on the performance of the partitioning algorithm (the way we select the pivot). In the worst case scenario, your partitioning algorithm might pick the lowest or the highest number in the unsorted array, then the Quick sort algorithm may end up with O(n²) complexity. However, if we can find a way that we can find the median element in the array in linear time, then running time of Quick sort will be (nlogn).

Since partitioning is so crucial for Quick sort, my question is: Can we find the median element in an unsorted array in linear time? If so, how? Please discuss the approach here. If not, then please explain why you think that it is not possible.