Quick Sort Vs Merge Sort

Why might quick sort be better than merge sort ?

See Quicksort on wikipedia:

> 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.

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.

For Merge sort worst case is O(n*log(n)), for Quick sort: O(n²). 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.

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.

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, however, was random and quick sort performs well if the data is random where as its not the case with merge sort i.e. merge sort performs the same, irrespective of whether 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.

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.

Quicksort is in place. You just need to swap positions of data during the Partitioning function. Mergesort requires a lot more data copying. You need another temporary storage (typically the same size as your original data array) for the Merge function.

quicksort is named so for a reason ,

highlights : both are stable sorts,(simply an implementation nuisance ) , so lets just move on to complexities

its very confusing with just the big-oh notations being spilled and "abused" , both have average case complexity of 0(nlogn) ,

but merge sort is always 0(nlogn) , whereas quicksort for bad partitions, ie skewed partitions like 1 element-10 element (which can happen due to sorted or reverse sorted list ) can lead to a 0(n^2)..

.. and so we have randomized quicksort , where we pick the pivot randomly and avoid such skewed partitioning , thereby nullifying the whole n^2 scenario anyway even for moderately skewed partitioning like 3-4 , we have a nlog(7/4)n, ideally we want 1-1 partion , thus the whole 2 of O(nlog(2)n).

so it is O(nlogn) , almost always and unlike merge sort the constants hidden under the "big-oh" notation are better for quicksort than for mergesort ..and it doesnt use up extra space like merge sort.

but getting quicksort run perfectly requires tweaking ,rephrase , quicksort provides you opportunities to tweak ....

The answer would slightly tilt towards quicksort w.r.t to changes brought with DualPivotQuickSort for primitive values . It is used in JAVA 7 to sort in java.util.Arrays

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

You can find the JAVA7 implmentation here - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Further Awesome Reading on DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

It is not true that quicksort is better. ALso, it depends on what you mean better, memory consumption, or speed.

In terms of memory consumption, in worst case, but quicksort can use n^2 memory (i.e. each partition is 1 to n-1), whereas merge sort uses nlogn.

The above follows in terms of speed.

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).