Calculate the efficiency of Quick sort. 

Ans:
Efficiency of Quick sort
Assume that the file size n is a power of 2
say n=2m
m=log2n (taking log on both sides)................. (A)
Assume also that the proper position for the pivot always turns out to be exact middle
of the sub array. In that case, there will be approx n comparisons (actually n-1) on the
first pass, after which the file is split into two sub files each of size n/2. Each of them
will have n/2 comparisons and file is again split into 4 files each of size n/4 and so on
halving it m times.
Proceeding in this way:-
No. of comparisons
1. file of size n 1*n=n
2. file of size n/2 2*n/2=n
3. file of size n/4 4*n/4=n
...
...
n file of size 1 n*1=n
Total no. of comparisons for entire sort
= n+n+n+.......+n (m times)
= nm
=n log2n (from A)
Therefore the efficiency of Quick sort is O (n log2n).