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