Quick Sort Vs 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.

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.