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.
