On the distribution of comparisons in sorting algorithms (Q1115198)

We consider the following natural conjecture: For every sorting algorithm every key will be involved in \(\Omega\) (log n) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involve \(n-n^{\epsilon}/2+1\) keys in at least \(\epsilon\) \(log_ 2 n\) comparisons, \(\epsilon >0\). Further, there exists a sorting algorithm that will for every input involve at most \(n-n^{\epsilon /c}\) keys in greater than \(\epsilon\) \(log_ 2 n\) comparisons, where c is a constant and \(\epsilon >0\). The conjecture is shown to hold for ``natural'' algorithms from the literature.