The characterization of sort sequences

A sort sequenceS _n is a sequence of all unordered pairs of indices inI _n = 1, 2, ...,n. With a sort sequenceS _n, we associate a sorting algorithmA(S _n) to sort input setX = x ₁, x₂, ..., x_n as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS _n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S _n) denote the average number of comparisons required by the algorithmA(S _n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S _n) over all sort sequencesS _n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n).