Quick Sort Vs Merge Sort

Question

Why might quick sort be better than merge sort

User · Accepted Answer

See Quicksort on wikipedia      Typically  quicksort is significantly   faster in practice than other T 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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

[algorithm] Quick Sort Vs Merge Sort

Examples related to algorithm

Examples related to sorting