[shamieh]

Given that quick sort has the same average case performance but worse worst case performance, why
might
someone prefer quick sort to merge sort? What does the merge sort implementation do that
the quick sort implementation not do?

This post has been edited by macosxnerd101: 18 September 2013 - 09:40 PM
Reason for edit:: Renamed title to be more descriptive

[Adak]

Quicksort is widely preferred, because:

1) It's easy to optimize (OK, not EZ, but it CAN be done, to great benefit). Just adding a call to Insertion sort for the smallest sub-arrays, gives a 12% improvement in run-time, typically.

2) It uses a minimum of program memory, if it's handling the smaller sub arrays it generates, first.

3) The complexity may be the same, but it's "n" is smaller than merge sorts "n", because it has favorable locality of reference. More often the data it needs, is in the (much) faster cache memory.

Since it's invention, Quicksort has been improved several times, at the algorithmic level. Mergesort CAN be made very fast - but you have to tweak it for A particular computer system, at a VERY low level, and the result is hundreds of line of code, that you wouldn't even recognize as being Mergesort.

This description is from the winners of the famous "Penney Sort" championship, who used Mergesort, btw.

In my tests, using a single thread, Mergesort has never equaled the run-time of Quicksort, even without optimizations, on a large array of random numbers. This is over hundreds of tests, on three different PC's, and 2 different OS.

There are old style Quicksorts that perform roughly the same as Mergesort, however. It's not a matter of optimization here, (there is none), but a matter of not having a modern algorithm for Quicksort.

[macosxnerd101]

Moved to Computer Science.

Mergesort is better than Quicksort at sorting Linked Lists. One key difference is that Mergesort doesn't require extra memory for partitioning Linked Lists, while Quicksort does. Mergesort also doesn't handle swap elements like Quicksort does; rather, Mergesort reinserts elements in sorted order.