最少比较排序问题中S(15)和S(19)的解决

The results of S(15) and S(19) to minimum-comparison sorting problem

最少比较排序问题就是要研究在最坏情况下,对n个元素完成排序所需要的最少比较次数S(n)。1965年M.Wells用穷举法证明了S(12)=30。2002年和2004年,M.Peczarski通过计算先后得到S(13)=34,S(14)=38,S(22)=71。文章在Wells算法和Peczarski算法基础上,设计了一个新的PS算法,并改进了线性扩展计数算法,在并行机"南开之星"上计算得到S(15)=42,S(19)=58。

The minimum-comparison sorting is the problem of finding the minimum number of key comparisons needed to sort n elements in the worst case. Let S(n) be the minimum number of comparisons that will suffice to sort n elements. M.Wells found that S(12)=30 by an exhaustive search in 1965. With the help of parallel computer,M.Peczarski improved Wells algorithm and proved that S(13)=34,S(14)=38 and S(22)=71 in 2002 and 2004 respectively. The authors extend both Wells algorithm and Peczarski algorithm. Some new results that S(15)=42 and S(19)=58 are first proved on a parallel computer named NKStars.