Intuit Interview Question
Senior Software Development EngineersCountry: United States
merge sort reserves some space by default. which is not the case with quick sort.
but there is no best case scenario in quick sort. even when the list is sorted the time complexity would be nlog(n).
The choice of algorithm depends on the scenario. If we expect the values to be nearly sorted and space is not a constraint, heap sort it is, else quick sort.
1.Quick sort is better than Merge sort in terms of space. It does not use additional storage space to perform sorting. In merge sort, to merge the sorted arrays it requires a temporary array means extra storage space.
2. Quick sort 2 3 times faster than any other sorting algo. Even though it's worst case is O(n^2) , it can be easily avoided by choosing right pivot.
I was asked the same question in some other interview recently. The above answer won't nearly answer what the interviewer might be looking for. Merge Sort is a stable algorithm where as Quick Sort is not a stable algorithm.
- None April 03, 2016The new point I learnt from the interviewer was, in Java, Collections.sort() method uses both Merge and Quick sort depending on what it's sorting. For example, if Integers are being sorted, then it seems Quick Sort is invoked. If object references are being sorted, then Merge Sort is invoked. And the pattern used here is Delegate.