ian@psuvax1.UUCP (Ian Parberry) (07/03/85)
In Knuth "The Art of Computer Programming", Volume 3, Section 5.3.4, there is a list of the best known upper and lower-bounds (at the time of publication) on the size and depth of sorting networks with up to 16 inputs. The optimal size and optimal depth are known for n<=8. Has any more progress been made for n>8 in the last 12 years? I am particularly interested in n=9,10,...16, but any "small" n will do. P.S. Yes, I do know about the Ajtai, Komlos and Szemeredi result, and the subsequent improvements by Mike Paterson. Even Batcher's sorting networks beats the latter for "small" n (the last figure I heard bandied about was 2 to the power 1300).