# what is the difference between merge sort and quick sort ?

3,278 views
what is the difference between merge sort and quick sort ?
posted Sep 4, 2013

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.

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.