What is the worst case time complexity of median of medians quicksort ( pivot is determined by the median of medians which take O(n) time to find )?
The approximate median-selection algorithm can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(n log n).
This is because the median of medians algorithm prevents the bad partitioning that would occur in naive quicksort on an already sorted array.