what is the different between merge sort and quick sort?



Statistically both MergeSort and QuickSort have the same average case time: O(nlog(n)); However there are 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

Read more:


Among those three, you can automatically discard bubble sort as the worst in general cases (it actually performs quite well when the list of numbers are already in order, unlike quick sort).

In general, merge sort is O(n log n) and quick sort is O(n log n). The two main differences are that 1) quick sort can have a degradation in performance if the pivot point is chosen poorly (O(n2)), 2) quick sort does not require the extra storage that merge sort does.

While I'm not an algorithms expert, I do know that most people tend to err on the side of using quick sort. I have never actually seen anyone implement a merge sort when they had a choice.

Answered by: siva85     On: 11-Apr-2011

Dear Guest,
Spend a minute to Register in a few simple steps, for complete access to the Social Learning Platform with Community Learning Features and Learning Resources.
If you are part of the Learning Community already, Login now!