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

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

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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

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

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

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.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Hunter

"If the facts don't fit the theory, get new facts" --Albert Einstein