Yahoo Interview Question Software Engineer / Developers
merge sort is not stable sort, .i.e, it needs external storage O(n) to do the merge.
quick sort is stable sort. So if memory is limited, use quicksort.
Merge sort IS stable (which means: always N log N, no matter what the input looks like).
At the same time yes indeed it takes some extra storage/memory.
So: if stability is essential (cannot tolerate worst-case scenario for qsort) and some storage is available, consider merge.
Quick sort sorts in place while merge sort requires extra storage of O(n). For Quick sort worst case performance is theta(n^2) while in case of merge sort it is always O(n).
1. If inplace sorting is required quick sort is best option.
2. If input data is baised and follows a particular pattern then Quick sort may not give you O(nlon(n)) performance. In that case merge sort or randomized quick sort can be used.
complexity: merge sort: average and worst case o(nlogn); quick sort: average O(nlogn), worst case O(n^2);
Space: merge sort: extra space; quick sort: in place
Stability: merge sort: stable; quick sort: not stable
Best fit: merge sort: slow seqential media; quick sort: general purpose.
Merge sort is often the best choice for sorting a linked list.
- warlock May 15, 2008