Median of medians Algorithm - [Linear Time O(n)] #PART-2

Median of medians can be used as a pivot strategy in quicksort, yielding an optimal algorithm.

10, 1, 67, 20, 56, 8 ,43, 90, 54, 34, 0

for this array the median will be 34.

0 1 8 10 20 34 43 54 56 67 90

Now the naive solution for this problem would be something like, first you sort the array, and then get the middle index element. But that approach does more work than required, as you just need to find the median, there's no need to know the sorted position of each element in the array.
and the worst time complexity for this solution is O(nlogn)

There's another solution for this problem that has complexity O(n), which is based on quick sort algorithm. so what we do,

we choose a pivot element,
then rearrange numbers exactly like we used to do in quick sort
then we return the pivot index.

Now we check if the index is the middle index.
if it is, we have found the median
if pivot index is less than median index, we recursively search for the median in right subarray.
else if pivot index is greater than median index, we recursively search in the left subarray.

[shubhayandas]

In the base condition, as we are soring the whole array, why is the time complexity not nlogn?

[akm]

I have a quick question. Wasn't the whole purpose of this method not to sort? When you sort the smaller arrays with 5 elements to find the median, doesn't that make the time back up again to nlogn? Thank you for your explanation by the way!