Translate

Visit to www.mrmcse.com

01 April 2018

What are the difference between quick sorts and merge sort



Quick sort
Merge sort
(i) Quick sort is another divide and conquer sorting algorithm, proposed by C. A. R. Hoare. Here, the work of quick sort is done by the partition operation.
(i) The real work of merge sort is done by the merge operation.
(ii) Quick sort cannot be implemented iteratively.
(ii) Merge sort can be implemented iteratively.
(iii) If the array is already sorted, the pivot will get placed in the left most position always and quick sort will be sorting sub-lists of size 0 and n-1. This leads to a time complexity of O (n^2). 
(iii) If we analyze the time complexity of merge sort, we will see it is O (n log n) in all cases. Merge sort also needs an extra array of size n for the merge operation is O (n).
(iv) Quick sort is one of the fastest algorithms an average.
(iv) Merge sort is less fast algorithm than quick sort.
(v) Quick sort does not need additional memory.
(v) Merge needs additional memory for merging.



No comments:

Post a Comment