GRE Practice Test Q 52 - Sort Run Time wrt Input Ordering

[dwarf]

Well the best case for merge sort is C1 n log n (if you solve the recurrence it is close to be 1/2 n log n). The worst case is C2 n log n (where C2 = 1).

If you see the difference, it is n logn - 1/2 n log n = 1/2 n log n = 50% more comparisons.

According to wikipedia it is actually 26.45% more compared to the average case.

For Selection Sort, if I take your argument to be true, then best case = n^2.
Worst Case = n^2 + n. (no difference in constant for the higher order term n^2).

If n = 600 (which is very low for real inputs)
n^2 + n is only 0.167% more than n^2.

Now which is faster, 24% more comparisons than the average case (or 50% more than the best case) or 0.1% more than the worst case. The difference is even more pronounced if you take n = 6 million.

In my humble opinion the answer to this question by ETS... needs to be revised.!