Microsoft Interview Question Software Engineer / Developers
* Quicksort is in place sorting
* Mergesort requires O(n/2) additional space, while merging just make a copy of the left (1st) array: no need to make a complete copy
* Heapsort does not offer any advantages I think over the above 2 if the sorted elements are static but if they can change then maintaining the heap property takes O(lg N) time.
Quick sort doesnt take extra space. You can pass pointer to array since all the partitions are disjoint
Stabilty is one more point :
> In-place quick sort in not stable you can code stable quick-sort ,but Merge-sort is stable sort > heap sort have all case running time o(n*log n) same as quick sort but constant factor of heap-sort is big
> Merge sort is better for external sort if your data does not fit in memory
Heapsort shall be used if you dont have any extra space. Quicksort requires extra log(n) space whereas MergeSort requires extra 'n' space.
- Sukku April 17, 2007Apart from this, worst case scenario of quick sort is O(n*n), when array is sorted in reverse order...whereas Heap sort works well in all the cases. I prefer Heap sort because it is inplace sorting and performs well in worst case. However depending on iput type once can choose any sorting algo.