views:

11793

answers:

16

I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?

+23  A: 

Actually, QuickSort is O(n^2). Its average case running time is O(nlog(n)), but its worst-case is O(n^2), which occurs when you run it on a list that contains few unique items. Randomization takes O(n). Of course, this doesn't change its worst case, it just prevents a malicious user from making your sort take a long time.

QuickSort is more popular because it:

  1. Is in-place (MergeSort requires tons of extra memory).
  2. Has a small hidden constant.
Dark Shikari
Actually, there are implementation of QuickSort which are O(n*log(n)), not O(n^2) in the worst case.
J.F. Sebastian
It also depends on the computer architecture. Quicksort benefits from the cache, while MergeSort doesn't.
Cristian Ciupitu
@J.F. Sebastian: These are most probably introsort implementations, not quicksort (introsort starts as quicksort and switches to heapsort if it is about to stop being n*log(n)).
CesarB
You can implement a mergesort in place.
Marcin
@Dark Shikari, I have made some corrections by editing your answer directly. See this page for a clear demonstration of the clarifications: http://www.sorting-algorithms.com/quick-sort In summary default quicksort is worst on a list with few unique items, not a reverse sorted list. Therefore this cannot be avoided by ensuring the list is randomly ordered.
Ash
+3  A: 

Quicksort is the fastest sorting algorithm in practice but has a number of pathological cases that can make it perform as badly as O(n2).

Heapsort is guaranteed to run in O(n*ln(n)) and requires only finite additional storage. But there are many citations of real world tests which show that heapsort is significantly slower than quicksort on average.

Niyaz
A: 

Quicksort has a better average case complexity but in some applications it is the wrong choice. Quicksort is vulnerable to denial of service attacks. If an attacker can choose the input to be sorted, he can easily construct a set that takes the worst case time complexity of o(n^2).

Mergesort's average case complexity and worst case complexity are the same, and as such doesn't suffer the same problem. This property of merge-sort also makes it the superior choice for real-time systems - precisely because there aren't pathological cases that cause it to run much, much slower.

I'm a bigger fan of Mergesort than I am of Quicksort, for these reasons.

Simon Johnson
+1  A: 

From the Wikipedia entry on Quicksort:

Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case Θ(nlogn) 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 Θ(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only Θ(logn) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)

gnobal
+3  A: 

Wikipedia's explanation is:

Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the probability of requiring quadratic time.

Quicksort

Mergesort

I think there are also issues with the amount of storage needed for Mergesort (which is Ω(n)) that quicksort implementations don't have. In the worst case, they are the same amount of algorithmic time, but mergesort requires more storage.

Mat Mannion
A: 

While they're both in the same complexity class, that doesn't mean they both have the same runtime. Quicksort is usually faster than mergesort, just because it's easier to code a tight implementation and the operations it does can go faster. It's because that quicksort is generally faster that people use it instead of mergesort.

However! I personally often will use mergesort or a quicksort variant that degrades to mergesort when quicksort does poorly. Remember. Quicksort is only O(n log n) on average. It's worst case is O(n^2)! Mergesort is always O(n log n). In cases where realtime performance or responsiveness is a must and your input data could be coming from a malicious source, you should not use plain quicksort.

D.J. Capelis
+2  A: 

I'd like to add that of the three algoritms mentioned so far (mergesort, quicksort and heap sort) only mergesort is stable. That is, the order does not change for those values which have the same key. In some cases this is desirable.

But, truth be told, in practical situations most people need only good average performance and quicksort is... quick =)

All sort algorithms have their ups and downs. See Wikipedia article for sorting algorithms for a good overview.

Antti Rasinen
+3  A: 

Mu! Quicksort is not better, it is well suited for a different kind of application, than mergesort.

Mergesort is worth considering if speed is of the essence, bad worst-case performance cannot be tolerated, and extra space is available.[1]

You stated that they «They're both O(nlogn) […]». This is wrong. «Quicksort uses about n^2/2 comparisons in the worst case.»[1].

However the most important property according to my experience is the easy implementation of sequential access you can use while sorting when using programming languages with the imperative paradigm.

[1] Sedgewick, Algorithms

Roman Glass
+25  A: 

You should also have a look at Introsort. It uses a very neat trick to push QuickSort's worst case down to O(n log n) while maintaining the other good performance characteristics. This is also why introsort is used in many modern “default” sorting implementations.

Basically, what it does is count the recursion depth. If a logarithmic depth is exceeded, the algorithm switches to Heapsort instead.

Another very good implementation is randomized QuickSort. And unlike suggested by Dark Shikari, randomization does not take additional preprocessing time. (The pivot element is chosen randomly.) Yes, this is actually the same performance overhead but Dark Shikari's text makes it look expensive while it really isn't, it just adds a very small constant factor.

Konrad Rudolph
The Wikipedia article states it switches to heapsort, not mergesort...just FYI.
Sev
@Sev: … as does the orignal paper. Thanks for pointing out the mistake. – Not that it really matters, since their asymptotic running time is the same.
Konrad Rudolph
+8  A: 

The Animated Sorting Algorithms shows a number of algorithms on 4 different initial conditions and might help.

liamvictor
I was going to link this! I LOVE LOVE LOVE this page. It is one of my favorite things. :)
Jeff Atwood
this is also cool! http://www.sorting-algorithms.com/
RCIX
A: 

Quicksort is NOT better than mergesort. With O(n^2) (worst case that rarely happens), quicksort is potentially far slower than the O(nlogn) of the merge sort. Quicksort has less overhead, so with small n and slow computers, it is better. But computers are so fast today that the additional overhead of a mergesort is negligible, and the risk of a very slow quicksort far outweighs the insignificant overhead of a mergesort in most cases.

xpda
Your second sentence says "...mergesort is potentially far slower than ... mergesort". The first reference should presumaably be to quicksort.
Jonathan Leffler
A: 

In c/c++ land, when not using stl containers, I tend to use quicksort, because it is built into the run time, while mergesort is not.

So I believe that in many cases, it is simply the path of least resistance.

In addition performance can be much higher with quick sort, for cases where the entire dataset does not fit into the working set.

EvilTeach
Actually, if it is the qsort() library function you are talking about, it may or may not be implemented as quicksort.
Thomas Padron-McCarthy
No, `qsort` is guaranteed to be a quicksort implementation. However, that's the C algorithm. C++ additionally comes with the better `sort` function and this is usually not implemented in terms of QuickSort any more.
Konrad Rudolph
Konrad, sorry to be a bit anal about this, but where do you find that guarantee? I can't find it in the ISO C standard, or in the C++ standard.
Thomas Padron-McCarthy
Jason Orendorff
+2  A: 

As others have noted, worst case of Quicksort is O(n^2), while mergesort and heapsort stay at O(nlogn). On the average case, however, all three are O(nlogn); so they're for the vast majority of cases comparable.

What makes Quicksort better on average is that the inner loop implies comparing several values with a single one, while on the other two both terms are different for each comparison. In other words, Quicksort does half as many reads as the other two algorithms. On modern CPUs performance is heavily dominated by access times, so in the end Quicksort ends up being a great first choice.

Javier
+15  A: 

As many people have noted, the average case performance for quicksort is faster than mergesort. But this is only true if you are assuming constant time to access any piece of memory on demand.

In RAM this assumption is generally not too bad (it is not always true because of caches, but it is not too bad). However if your data structure is big enough to live on disk, then quicksort gets killed by the fact that your average disk does something like 200 random seeks per second. But that same disk has no trouble reading or writing megabytes per second of data sequentially. Which is exactly what mergesort does.

Therefore if data has to be sorted on disk, you really, really want to use some variation on mergesort. (Generally you quicksort sublists, then start merging them together above some size threshold.)

Furthermore if you have to do anything with datasets of that size, think hard about how to avoid seeks to disk. For instance this is why it is standard advice that you drop indexes before doing large data loads in databases, and then rebuild the index later. Maintaining the index during the load means constantly seeking to disk. By contrast if you drop the indexes, then the database can rebuild the index by first sorting the information to be dealt with (using a mergesort of course!) and then loading it into a BTREE datastructure for the index. (BTREEs are naturally kept in order, so you can load one from a sorted dataset with few seeks to disk.)

There have been a number of occasions where understanding how to avoid disk seeks has let me make data processing jobs take hours rather than days or weeks.

+1  A: 

All things being equal, I'd expect most people to use whatever is most conveniently available, and that tends to be qsort(3). Other than that quicksort is known to be very fast on arrays, just like mergesort is the common choice for lists.

What I'm wondering is why it's so rare to see radix or bucket sort. They're O(n), at least on linked lists and all it takes is some method of converting the key to an ordinal number. (strings and floats work just fine.)

I'm thinking the reason has to do with how computer science is taught. I even had to demonstrate to my lecturer in Algorithm analysis that it was indeed possible to sort faster than O(n log(n)). (He had the proof that you can't comparison sort faster than O(n log(n)), which is true.)

In other news, floats can be sorted as integers, but you have to turn the negative numbers around afterwards.

Edit: Actually, here's an even more vicious way to sort floats-as-integers: http://www.stereopsis.com/radix.html. Note that the bit-flipping trick can be used regardless of what sorting algorithm you actually use...

Anders Eurenius
I've seen my share of radix sorts. But it's pretty hard to use because if analyzed correctly, its runtime is *not* O(n) as it depends on more than the number of input elements. In general, it's very hard to make that kind of strong predictions that radix sort needs to be efficient about the input.
Konrad Rudolph
It *is* O(n), where n is the *total* input size, that is, including the size of the elements. It's true that you can implement it so you have to pad with a lot of zeroes, but it's nonsense to use a poor implementation for comparison. (That said, implementation can be hard, ymmv.)
Anders Eurenius
Note that if you're using GNU libc, `qsort` is a merge sort.
Jason Orendorff
Jason Orendorff
A: 

"and yet most people use Quicksort instead of Mergesort. Why is that?"

One psychological reason that has not been given is simply that Quicksort is more cleverly named. ie good marketing.

Yes, Quicksort with triple partioning is probably one of the best general purpose sort algorithms, but theres no getting over the fact that "Quick" sort sounds much more powerful than "Merge" sort.

Ash