what is the difference between merge sort and quick sort ?

Question

both seems to be same, can someone explain the difference with example and complexity?

Answer 1

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 2

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 3

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 4

**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.**