+1 vote
450 views
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 ?

| 450 views

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 ...
by Boss (17k points)
selected by
option (2) : Calling insertion sort for small sized arrays to reduce recursive calls
by Active (3.8k points)