Sort Sequences and Predictive Sorting Algorithms
Minyoung Yun · Journal of Electrical Engineering and Information Science · 1997
A sort sequence S_n is a sequence of all unordered pairs of indices in I_n= {1.2,....n}. With a sort sequence S_n we associate a predictive sorting algorithm A(S_n) to sort input set X= {X₁,X₂,...,X_n} as follows. An execution of the algorithm performs pairwise comparisons of elements in the input set X as defined by the son sequence, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. The efficiency of a sorting algorithm is defined by the expected number of pairwise comparisons required. In this paper predictive sorting algorithms are obtained, based on known sorting algorithms, and are shown to be required on the average O(nlog n) comparisons.