# MadeEasy Test Series: Algorithms - Sorting

1 vote
787 views
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($n^{2}$)
b.O(nlogn)
c.O($n^{2}$logn)
d.O(nloglogn)

edited
0
It should be O(nlogn) in worst case because, selecting median as pivot means it will be always  placed at the middle after applying partition algorithm.
0
B is the correct option

Because for every split occur at the middle .
0
0
what is that means[ Pivot is the median of set of 3 elements ].

1 vote
Worst case would be Θ($n^2$) because input array given is already sorted.

reshown
1
0
i think O(nlogn) is right answer....
1 vote
B should be the correct option.
1 vote
Option B is the correct answer.

lets consider an array 1,2,3,4,5

according to the question median of an array = median(1,3,5)= 3.

so the array is divided into almost equal halves and for that time complexity would be O(nlogn)
option B) O(nlogn) is correct , because everytime array is divided into almost equal parts.

## Related questions

1 vote
1
583 views
Is there any standard way to sort in Quicksort or what all matters is PIVOT getting placed at its correct position thats it? I mean if only pivot condition then 3!*3! for both left and right elements but if any standard then each of the left and right parts ... fixed way that after 1st pass the array will remain as it is and only those elements compared with the minimum will be getting swapped.