Consider a scenario of modified quick sort, where we have given an input sorted array A[1 . . . n], all elements of array are distinct and n ≥ 3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity of modified quick sort?
a)$O\left ( n^{2} \right )$
b)$O\left ( n log n \right )$
c)$O\left (n^{2} log n \right )$
d)$O\left (nlog log n \right )$
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
My doubt is here for every 3 element we have to apply quick sort, rt? So, in modified quick sort we can do first quick sort and then merging using merge sort.rt?