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