Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are same like (2,2,2,2,....,2) and pivot is still the median element, then what type of partitions QS will get as left and right subarray and what will be the time complexity. O(nlogn) or O(n^2)
This is not a homework question, I'm not in school/college anymore.
It depends on the partition algorithm used. Some might be $O(n^2)$ if they put all equal elements on the same side while others remain $O(n \log n)$ if they split the equal elements.
Writing a Quicksort implementation where n equal items take $O(n^2)$ is just stupid.
A good implementation will split the array into items less than the median, equal to the median, and greater than the median. That will sort an array of all equal elements in O(n).
