What is the {best|average|worst}-case time for
Mergesort to sort an array of n records?
\Theta(n \log n)\Theta(n)\Theta(\log n)\Theta(n^2)\Theta(n^n)Does Mergesort's number of comparisons depend on the particular order of the input array?
No, it does not.