Quicksort vs Merge Sort

Hi,

I have just started learning algorithms and went through merge sort and quick sort.Run time analysis states that both have an O(n log n) time for best cases. Where does the difference lie? I wonder if it could be in the number of comparisons. Considering a real world application where an array has a considerable length and some part of it is in order, when would I want to choose a quick sort over a merge sort(keeping aside the fact that merge sort needs additional storage in terms of auxillary array).

Thanks much

memory is one reason. complexity to code is another, if you are writing it yourself.

Also, while the 'best case' for each is the same, the 'worst case' is vastly different...N^2 for quick, nlogn for merge. If you know your data is likely to be in quick-sort's worst case order, I wouldn't pick it.

Merge sort is also a stable sort - quick sort may or may not be

Thanks Fred for the answer. Quick sort as per my knowledge solely depends on what your bound/pivot is, so that when you sort the members of your array you get balanced right and left arrays. Merge sort on the other hand makes this comparison after dividing a large array into single elements and then compares them.

I am looking for an example (may be a real world ex) where computational times of quick sort is better than merge sort. Let's say merge sort has its worst case and quick sort its best. Will quick sort be able to beat merge sort in computational times when both have an upper bound of O(n log n)?

But as Fred said, the upper bound (the worst case) for quicksort is O(n^2), not O(n log n).

Wikipedia contains a lot of details about quicksort. Note that there's a paragraph "Comparison with other sorting algorithms", where it is compared with other algorithms, one of which is merge sort:

Wikipedia wrote:Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case O(n log n) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that, when operating on arrays, it requires O(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only O(n log n) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)

So, the main advantage of quicksort over merge sort is that it requires less memory.

Both quicksort and merge sort have an average complexity of O(n log n), so you shouldn't expect quicksort to be faster on average than merge sort.

I also believe quick sort generally has a lower constant factor, overall making it slightly faster than merge sort for average case scenarios.

I know that the main reason Collections uses merge sort rather than quick sort is because merge sort is stable. I've also read somewhere (I forgot where) that enhanced heap sort might be a good contender for becoming the sorting algorithm of choice for a lot of programs.

I don't see how heap sort would outperform merge sort, because you have to consider the cost of creating/maintaining the heap in addition to the cost of the actual sorting.

Hunter

And yet its worst case is O(n log n). Reheaping (or fixheaping) is remarkably efficient. It's also in-place.

The main disadvantage is that it's not stable. None of these algorithms are clearly better than another. They have their uses in specific scenarios. Merge sort is stable, and it parallelizes well. Quick sort is quick. Heap sort uses constant memory.

One thing that should probably be made clear...

Just because two algorithms have the same Big-O notation doesn't mean they will run in the same time. Big-O ignores a bunch of stuff, like constants and factors in front of the significant terms.

So if the constants are different, the performance will be different. If some of the lower-order terms are different, which one is faster may STILL depend on the size of the items to be sorted. One will be faster below a certain size and the other may be faster above a certain size.

To illustrate, even though insertion sort has a complexity in O(n^2), it is faster than merge/quick sort for small lists. That's why merge sort usually breaks down a big list into smaller ones that are typically around 10 elements long, which are then sorted using insertion sort, before the merge sort proceeds to merge them.

I didn't mean to imply that there isn't a situation where heap sort would outperform merge sort, I'm sure there is some situation in which it would. I just wanted to point out that there were other factors to consider with heap sort. Regardless of how efficient the reheaping algorithm is it still takes time and has to be performed often in heap sort.

Hunter