Why might quick sort be better than merge sort ?
and the downvote was because?
Mitch Wheat
2009-03-25 07:38:26
It's not from me, but you just give a link with a huge amount of text, but the requested piece of information isn't on the page at all.
Georg
2009-03-25 07:49:59
@gs: it is. The pros and cons of each can be worked out from the table listed there.
Mitch Wheat
2009-03-25 09:32:55
+7
A:
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.
Note that the very low memory requirement is a big plus as well.
Benoît
2009-03-25 07:32:31
If the quicksort is initialized up front with a random 64-bit number *N*, and the pivot for every section is at index *N* mod *SectionSize*, then the probability of the algorithm demonstrating any complexity C where C is worse than O(n log n) exponentially decreases as the input size grows.
280Z28
2009-10-13 02:35:16
+6
A:
For Merge sort worst case is O(n*log(n)), for Quick sort: O(n2). For other cases (avg, best) both have O(n*log(n)). However Quick sort is space constant where Merge sort depends on the structure you're sorting.
See this comparison.
You can also see it visually.
Marcin Gil
2009-03-25 07:32:42
In-place quicksort in fact uses O(nlog n) space on average (and as much as O(n^2) in the pathological worst case), because it needs to store a constant amount of information on the stack per recursive invocation.
j_random_hacker
2009-03-26 07:58:14
That is wrong. An acceptable implementation of quicksort sorts smallest subrange first.
Stephan Eggermont
2009-12-13 21:59:23
Very good comparison article indeed. Both explanation and simple implementations.
extraneon
2010-04-08 08:05:50
@Stephan Eggermont: You're right -- quicksort uses at least O(log n) and at most O(n) extra *space*, since every split (recursion) requires constant space to store the pivot location and there must be at least log2(n) of them. I must have got confused and put the extra factor of n in by mistake.
j_random_hacker
2010-10-30 07:00:08
+3
A:
While quicksort is often a better choice than merge sort, there are definitely times when merge sort is thereotically a better choice. The most obvious time is when it's extremely important that your algorithm run faster than O(n^2). Quicksort is usually faster than this, but given the theoretical worst possible input, it could run in O(n^2), which is worse than the worst possible merge sort.
Quicksort is also more complicated than mergesort, especially if you want to write a really solid implementation, and so if you're aiming for simplicity and maintainability, merge sort becomes a promising alternative with very little performance loss.
CaptainAwesomePants
2009-03-25 07:58:43
Where mergesort shines is when you need either a stable sort (elements that compare equal are not rearranged) or when you are using sequential (rather than random-access) "memory" (e.g. you can mergesort efficiently using tape drives).
j_random_hacker
2009-03-26 08:00:22
@j_random_hacker: your tape drive example is a bit obscure; more common examples might be sorting data as it is received from a network connection, or sorting data structures which don't allow efficient random access like linked lists
Christoph
2010-10-29 07:46:00
A:
Quicksort is in place. You need very little extra memory. Which is extremely important.
Good choice of median makes it even more efficient but even a bad choice of median quarantees Theta(nlogn).
But quicksort requires random access to all the data which might not be ideal for very large data sets
Martin Beckett
2009-10-13 02:12:54
+1
A:
I personally wanted to test the difference between Quick sort and merge sort myself and saw the running times for a sample of 1,000,000 elements.
Quick sort was able to do it in 156 milliseconds whereas Merge sort did the same in 247 milliseconds
The Quick sort data was, however, was random and quick sort performs well if the data is random where as its not the case with merge sort ie merge sort performs irrespectively the same when data is sorted or not. But merge sort requires one full extra space and quick sort does not as its an in-place sort
I have written comprehensive working program for them will illustrative pictures too.
Bragboy
2010-02-14 08:41:39
+1
A:
In addition to the others: Merge sort is very efficient for immutable datastructures like linked lists and is therefore a good choice for (purely) functional programming languages.
A poorly implemented quicksort can be a security risk.
Dario
2010-02-14 09:21:58
the issue with linked lists is not mutability, but lack of efficient random access, ie you're stuck with on-line algorithms (merge sort, insertion sort)
Christoph
2010-10-29 07:41:55
A:
Quick sort is typically faster than merge sort when the data is stored in memory. However, when the data set is huge and is stored on external devices such as a hard drive, merge sort is the clear winner in terms of speed. It minimizes the expensive reads of the external drive and also lends itself well to parallel computing.
Michael
2010-04-08 07:35:47