top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

what is the difference between merge sort and quick sort ?

+2 votes
3,712 views
what is the difference between merge sort and quick sort ?
posted Sep 4, 2013 by Vikram Singh

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

4 Answers

+2 votes

In worst case Quicksort will have O(n^2) where Mergesort will be O(n*log n)

Quicksort uses a pivot and sorts the two parts with the pivot as reference point with the risk that the pivot will be either maximum or minimum of the sorted array. If you will be choosing the wrong pivots you will end up with complexity n^2 (n^2 comparsions)

Mergesort as named is based on recursively dividing array into halfs of the same size and merging them back. Pretty nice explanations on wikipedia ( http://en.wikipedia.org/wiki/Merge_sort ) for example. Especially the picture with the tree-like brakedown seems to explain it pretty well.

answer Sep 4, 2013 by anonymous
+1 vote

Statistically both MergeSort and QuickSort have the same average case time: O(nlog(n)); However In worst case Quicksort will have O(n^2) where Mergesort will be O(n*log n) though there are other various differences.

Most implementations of Mergesort, require additional scratch space, which could bash the performance. The pros of Mergesort are: it is a stable sort, and there is no worst-case scenario.

Quicksort is often implemented inplace thus saving the performance and memory by not creating extra storage space. However the performance falls on already sorted/almost sorted lists if the pivot is not randomized.

answer Sep 5, 2013 by Salil Agrawal
0 votes

Both MergeSort and QuickSort have the same average case time: O(nlog(n)); However In worst case Quicksort will have O(n^2) where Mergesort will be O(n*log n) though there are other various differences.
Most implementations of Mergesort, require additional scratch space, which could bash the performance. The pros of Mergesort are: it is a stable sort, and there is no worst-case scenario.
Quicksort is often implemented inplace thus saving the performance and memory by not creating extra storage space. However the performance falls on already sorted/almost sorted lists if the pivot is not randomized.

answer Mar 9, 2016 by Ashish Kumar Khanna
0 votes

**Quick sort does not require any additional memory while executing. It just sorts everything in the very array where the unsorted elements are present. On the other hand Merge sort requires extra memory (a lot of memory if the array is large). And the amount of extra memory required is O(n) which means it is directly proportional to the input size n.

"Quick Sort is NOT a stable sorting algorithm while Merge is." Quick sort is not stable because it exchanges the non adjacent elements. So preservance of order is not taken care of. The result might be stable or unstable. While Merge is a stable sort.**

answer Mar 9, 2016 by Kritika Agarwal
...