1

I am aware that variants on merge-insertion sort aka the Ford–Johnson algorithm have the best known worst case performance, however their average case performance is very close to worst case. The simple merge sort, on the other hand, has much better best and average case performance. Is merge sort the best known algorithm with regards to average case number of comparisons, or is there a better one?

Vilim Lendvaj
  • 45
  • 2
  • Why not perform the counts on a large enough random sample of inputs? – trincot Aug 13 '23 at 17:05
  • Counting sort has 0 comparisons, so is best. – stark Aug 13 '23 at 22:54
  • @trincot because I know the answer for all sorting algorithms I know of and I'm asking about potential algorithms I don't know of. For example the Ford-Johnson algorithm is an algorithm that I've never heard of before starting this search and it's never used in practice, only to study worst case comparison count performance. I'm curious if there's such an algorithm optimized for the average case. – Vilim Lendvaj Aug 13 '23 at 23:17
  • The best you can hope to do on average is log_2(n!), or about n * (log_2(n) - 1.44). What did you get for average case merge sort? – Matt Timmermans Aug 14 '23 at 01:53
  • 1
    @MattTimmermans I see my error. I was sloppy in estimating the average case performance of merge sort, I didn't realize that the probability of savings decreases exponentially with the amount of savings so even though the best case is 0.5\*n\*log_2(n)+O(n), the average case is still 1\*n\*log_2(n)+O(n). Additionally, binary insertion sort is better than merge sort in both the worst and average case (and worse in the best case), and variations on the Ford–Johnson algorithm probably have the best average case eprformance just as they have the best worst case performance. – Vilim Lendvaj Aug 14 '23 at 12:16

0 Answers0