1

Assume I have N items in an un-ordered array that I need to sort, and that I support a comparison operation between items in the array, but it is very expensive, so I want to perform as few comparisons as possible. That is, I don't just want to pick a sorting algorithm with guaranteed O(n log n) comparisons, which can be up to a scale factor, I want to pick that algorithm which will use the fewest comparisons of all. What algorithm do I pick?

Void Star
  • 2,401
  • 4
  • 32
  • 57
  • 1
    Possible duplicate of [Which sorting algorithm uses the fewest comparisons?](http://stackoverflow.com/questions/13092548/which-sorting-algorithm-uses-the-fewest-comparisons) – Giorgi Nakeuri Oct 13 '15 at 06:06
  • If there are no known patterns in the input and comparison is the only way to rearrange the elements, I don't think we have a definitive answer for this. The CLRS book on algorithms provides a mathematical proof that Any comparison sort algorithm requires (n log n) comparisons in the worst case. This may not apply to sorting algorithms like counting sort, but they rely on operations other than comparison. Bottom line, we need to know more about the input to do better than (n log n). – ramana_k Oct 13 '15 at 06:16
  • It'll be n log n, but there's a constant factor multiplied out by that, and this is important to me. – Void Star Oct 17 '15 at 21:54

0 Answers0