Use the worst-case linear-time median finding algorithm to pick the pivot in the partitioning step of Quick sort. This guarantees an equal split in linear time, so the recurrence is T(n) = 2T(n/2) + Theta(n) = Theta(nlgn).
How many key comparisons would be performed in the worst case?
We perform lg i comparisons when inserting key i+1. The total number of comparisons in the worst case is .