使用合并排序的比较数

Question

如果您有5个不同的数字,那么您需要使用合并排序对此进行多少次比较？

Answer 1

什么阻止你编写合并排序,保持计数器中的比较数,并在[0,1,2,3,4]的所有排列上尝试？

Answer 2

我发现这个问题很有趣，所以我决定彻底探索它（在 Python 中进行一些实验）。

我mergesort.py从这里下载并修改它以添加cmp比较器函数的参数。然后：

import collections
import itertools
import mergesort
import sys

class CountingComparator(object):
  def __init__(self):
    self.count = 0
  def __call__(self, a, b):
    self.count += 1
    return cmp(a, b)

ms_histo = collections.defaultdict(int)

for perm in itertools.permutations(range(int(sys.argv[1]))):
  cc = CountingComparator()
  lperm = list(perm)
  mergesort.mergesort(lperm, cmp=cc)
  ms_histo[cc.count] += 1

for c in sorted(ms_histo):
  print "%d %2d" % (c, ms_histo[c])

生成的简单直方图（从长度 4 开始，正如我在开发和调试时所做的那样）：

4  8
5 16

对于发布的问题，长度为 5 而不是 4，我得到：

5  4
6 20
7 48
8 48

长度为 6（以及更宽的格式；-）：

7    8
8   56
9  176
10 288
11 192

最后，长度为 7（甚至更宽的格式；-）：

 9   16
10  128
11  480
12 1216
13 1920
14 1280

当然，这里潜藏着一些完全规则的组合公式，但我发现很难通过分析或仔细研究数字来判断它可能是什么。有人有建议吗？