• Post Reply Bookmark Topic Watch Topic
  • New Topic

Quicksort vs Merge Sort  RSS feed

 
Gagan Sabharwal
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I have just started learning algorithms and went through merge sort and quick sort.Run time analysis states that both have an O(n log n) time for best cases. Where does the difference lie? I wonder if it could be in the number of comparisons. Considering a real world application where an array has a considerable length and some part of it is in order, when would I want to choose a quick sort over a merge sort(keeping aside the fact that merge sort needs additional storage in terms of auxillary array).

Thanks much
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
memory is one reason. complexity to code is another, if you are writing it yourself.

Also, while the 'best case' for each is the same, the 'worst case' is vastly different...N^2 for quick, nlogn for merge. If you know your data is likely to be in quick-sort's worst case order, I wouldn't pick it.

Merge sort is also a stable sort - quick sort may or may not be
 
Gagan Sabharwal
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Fred for the answer. Quick sort as per my knowledge solely depends on what your bound/pivot is, so that when you sort the members of your array you get balanced right and left arrays. Merge sort on the other hand makes this comparison after dividing a large array into single elements and then compares them.

I am looking for an example (may be a real world ex) where computational times of quick sort is better than merge sort. Let's say merge sort has its worst case and quick sort its best. Will quick sort be able to beat merge sort in computational times when both have an upper bound of O(n log n)?
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But as Fred said, the upper bound (the worst case) for quicksort is O(n^2), not O(n log n).

Wikipedia contains a lot of details about quicksort. Note that there's a paragraph "Comparison with other sorting algorithms", where it is compared with other algorithms, one of which is merge sort:
Wikipedia wrote:Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case O(n log n) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that, when operating on arrays, it requires O(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only O(n log n) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)

So, the main advantage of quicksort over merge sort is that it requires less memory.

Both quicksort and merge sort have an average complexity of O(n log n), so you shouldn't expect quicksort to be faster on average than merge sort.
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I also believe quick sort generally has a lower constant factor, overall making it slightly faster than merge sort for average case scenarios.

I know that the main reason Collections uses merge sort rather than quick sort is because merge sort is stable. I've also read somewhere (I forgot where) that enhanced heap sort might be a good contender for becoming the sorting algorithm of choice for a lot of programs.
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't see how heap sort would outperform merge sort, because you have to consider the cost of creating/maintaining the heap in addition to the cost of the actual sorting.

Hunter
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And yet its worst case is O(n log n). Reheaping (or fixheaping) is remarkably efficient. It's also in-place.

The main disadvantage is that it's not stable. None of these algorithms are clearly better than another. They have their uses in specific scenarios. Merge sort is stable, and it parallelizes well. Quick sort is quick. Heap sort uses constant memory.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One thing that should probably be made clear...

Just because two algorithms have the same Big-O notation doesn't mean they will run in the same time. Big-O ignores a bunch of stuff, like constants and factors in front of the significant terms.

So if the constants are different, the performance will be different. If some of the lower-order terms are different, which one is faster may STILL depend on the size of the items to be sorted. One will be faster below a certain size and the other may be faster above a certain size.
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To illustrate, even though insertion sort has a complexity in O(n^2), it is faster than merge/quick sort for small lists. That's why merge sort usually breaks down a big list into smaller ones that are typically around 10 elements long, which are then sorted using insertion sort, before the merge sort proceeds to merge them.
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I didn't mean to imply that there isn't a situation where heap sort would outperform merge sort, I'm sure there is some situation in which it would. I just wanted to point out that there were other factors to consider with heap sort. Regardless of how efficient the reheaping algorithm is it still takes time and has to be performed often in heap sort.

Hunter
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!