• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Rob Spoor
  • Devaka Cooray
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Jj Roberts
  • Al Hobbs
  • Piet Souris

Quicksort vs Merge Sort

 
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
lowercase baba
Posts: 13013
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)?
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Saloon Keeper
Posts: 13367
295
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 492
Firefox Browser VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 13367
295
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 13013
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 13367
295
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic