Abstract: 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.

Key words: minimum-comparison sorting, optimal sorting, linear extensions counting

摘要： 最少比较排序问题就是要研究在最坏情况下,对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。

关键词: 最少比较排序, 最优排序, 线性扩展计数