I think all you need to know is that algorithms of this kind are called "sorting networks"; Google will do the rest. The Wikipedia article https://en.wikipedia.org/wiki/Sorting_network is a good start. On Wed, Jun 13, 2018 at 3:24 PM, Dan Asimov <dasimov@earthlink.net> wrote:

Consider all algorithms for sorting a permutation of {1, 2, 3, ..., N}, say given as a filled array arr[1], ..., arr[N], such that each step of the algorithm is of the form

if (arr[I] > arr[J]) swap(arr[I], arr[J]);

where I and J are actual numbers, and no other steps are allowed.

For instance, If x[1], x[2], x[3] is any permutation of {1, 2, 3} then this program will always sort it:

----- if (x[1] > x[2]) swap(x[1], x[2]);

if (x[2] > x[3]) swap(x[2], x[3]);

if (x[1] > x[2]) swap(x[1], y[2]); -----

Among those that sort all permutations of {1, 2, 3, ..., N}, what is the minimum number of comparisons that sort the worst-case permutation(s)?

Let this number be C(N). I'd like to have an asymptotic expression for C(N), or at least upper and lower bounds.

—Dan

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun