I know that quick sort has an average case of O(nlogn). And I also know that the average case of comparison-based sorting algorithms are Omega of nlogn. Can we say that quick sort is the best sorting algorithm in average case compared to other comparison-based sorting algorithms? (I think the answer is yes. However, I cannot justify my answer with a convincing argument)

  • $\begingroup$ Heap and merge-sort are also O(n log n) on average, so why would quick-sort be the best? $\endgroup$ – Peter Lenkefi Jun 26 '17 at 17:17
  • $\begingroup$ Please define "best". $\endgroup$ – Raphael Jun 26 '17 at 20:48

Depends. Quicksort is not one algorithm. Performance depends on the details. You would adjust the algorithm slightly if moving items is expensive.

You might assume that items are in random order. That is often not the case. You may be able to sort items with non-random items faster than using quicksort. For example if an array starts or ends with many items in ascending or descending order sorting in linear time may be possible.

  • $\begingroup$ Please let me know if you disagree that this is a duplicate! $\endgroup$ – Raphael Jun 26 '17 at 20:49
  • $\begingroup$ @gnasher729 About the first paragraph: This was a question in one of my exams a few month ago. The topic was time complexity and asymptotic notations. I'm pretty sure that implementation details were not important. About the second paragraph: Yes there are other sorting algorithms that sort in linear time. but they are not based on comparisons. $\endgroup$ – Amir Qasemi Jun 27 '17 at 7:35
  • $\begingroup$ @amir: The question wasn't about asymptotic behaviour. And there are comparison based algorithms that work in linear time in many practical cases - for example sorting already sorted arrays , which happens a lot in practice. $\endgroup$ – gnasher729 Jun 27 '17 at 19:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.