Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
there are few advantage of the quick sort over merge sort :
1. it is inplace .
2. it is most widely used algo. for any set of data.
3. in the worst case , whet the partition algorithm combined with the randomization , it becomes very power full.very less probablity of the worst case.
4. for settelite data it really performs well.
Merge sort always run at O(n log(n)). Quick sort can be O(n^2) in worst case scenario.
Merge sort cannot be done in-place (It is possible but the implementation is very hard), Quick sort can be done in-place a lot easier.
Which one is better? Quick sort, as long as we use randomize algorithm to randomize the quick sort pivot selection so that we can make the worst case runtime of O(n^2) virtually disappear.
those who are blaming quick sort for the worst case ,it will give worst case only when the array is sorted or almost sorted.
it is most practically used algo. and if the array is sorted ,why are you going for sorting !!?
IT IS TONY HOARE PRODUCT , MY FAV COMPUTER SCIENTIST , winner of turing award!
quick sort worst case , average case o(nlog n )only , and with randomization , it will give n log n , even in the worst case , for the 99% of the input sets , and bigger advantage over the merge is , it is outplace.
when someone comes to the sattelite data , using this is probably the worst idea !
There is one big advantage of merge sort over quick sort on modern multi-core architecture. Although both have average response time of (n log n), remember that because you have separate memory for the divisions in merge sort, you can safely run some operations in parallel where as in quick sort, unless you run first partition operation, you cannot run 2nd partition operation and therefore there are issues with making it parallel.
- PK February 18, 2015