normal vs randomized quicksort on an array which is 1/3 sorted

Question

I am trying to calculate a time complexity for applying quicksort (randomized or normal) on an array with these properties:
the array is unsorted in the first 2/3 , and the largest element is t
the next 1/3 is sorted, and all elements here are larger than t\

I understand that in a normal quicksort, selecting the barrier between these two parts results in not having to sort the next 1/3 , but I cannot find a formal (mathematical) way to calculate an asymptotic bound on the time complexity.
Thanks in advance

Answer 1

Randomised quicksort is equivalent to shuffling the array first and then applying naive quicksort. Shuffling takes linear time and makes it so that you get the average time complexity for quicksort regardless of the partially-sorted input, i.e. O(n log n).

Naive quicksort will have quadratic time complexity on these inputs because eventually the element t will be chosen as a pivot, and t occurs before the sorted region, so this region will be selected as a partition in its entirety. Naive quicksort will take quadratic time in (n/3) on this partition, which is quadratic in n.