3

First of all, I have done searching before posting this question. I've looked at the question at Why is quicksort better than mergesort? but it has a few contradictory answers.

Depending on where I look, people say quicksort is "faster" than mergesort due to its locality of reference, cache hits etc. Now, I accept this is important in practice but my question is purely about analysis - I'm not interested in recursion overhead, cache issues and the like. In addition answers are often vague as to what they mean when they say faster, I'm not sure if they're referring to time taken to execute and as such if cache issues are relevant to their answers.

Anyway, my question is simple. Purely in terms of the number of comparisons performed, is mergesort always more efficient than quicksort? Wikipedia tells me yes, which is what I've always thought, but as I said, other people say different things.

Community
  • 1
  • 1
user1520427
  • 1,345
  • 1
  • 15
  • 27

1 Answers1

3

Basic Quicksort, in the worst case, will run in O(n^2) time. Consider if the the pivot chosen is always the next smallest element, it is equivalent to Insertion sort. Mergesort doesn't have this difficulty.

Further, Mergesort is also stable, which means it preserves the order of equally valued elements (so it's good for sorting "first by this, then by that"), where's Quicksort is not.

The biggest drawback to Mergesort is that most implementations must be done with 2n space, whereas Quicksort can be done in-place (in case space is a problem in your application).

The individual wikipedias on both Quicksort and Mergesort are excellent, I recommend reading them.

durron597
  • 31,968
  • 17
  • 99
  • 158