Which of the following changes to typical QuickSort improves its performance on average and are generally done in practice ?

Question

1) Randomly picking up to make worst case less 
   likely to occur.
2) Calling insertion sort for small sized arrays 
   to reduce recursive calls.
3) QuickSort is tail recursive, so tail call 
   optimizations can be done.
4) A linear time median searching algorithm is used 
   to pick the median, so that the worst case time 
   reduces to O(nLogn)

I am not getting points 2 and having confusion in point 3 that how quicksort can be tail-recursive since we have 2 function calls at the end , and why is option 4 wrong ,since if we pick the pivot as median then surely It will divide the array equally into two halves therefore worst case time complexity must be O(n log n ) , plz correct me where am I wrong ?

Answer 1

these links may clear your doubt

http://www.geeksforgeeks.org/iterative-quick-sort/

http://stackoverflow.com/questions/12454866/how-to-optimize-quicksort

https://en.wikipedia.org/wiki/Quicksort#Optimizations

in 4th option we can use in theory but not in practice bcoz choose median as pivot in large array has many overhead ...

Answer 2

option (2) : Calling insertion sort for small sized arrays to reduce recursive calls

Answer 3

for the 4th option,

when the array is already sorted.....then applying the linear time median searching algorithm still results in O(n^2) time.

so, using linear time median searching algorithm we can achieve ϴ(n log n) but not O(n log n)....since there is a possibility of O(n^2).