The Gateway to Computer Science Excellence
+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 ?

in Algorithms by Loyal (6.3k points) | 450 views

2 Answers

+2 votes
Best answer
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 ...
by Boss (17k points)
selected by
0 votes
option (2) : Calling insertion sort for small sized arrays to reduce recursive calls
by Active (3.8k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,614 answers
195,893 comments
102,327 users