# Can the sorting of a list be verified without comparing neighbors?

A $$n$$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare every item with its neighbor: instead, the comparisons will sometimes be between distant elements. Given that the list contains more than three items and also that comparison is the only supported operation, does there ever exist a "network" of comparisons that will prove that the list is sorted, but is missing at least one direct neighbor-to-neighbor comparison?

Formally, for a sequence of elements $$e_i$$, I have a set of pairs of indices $$(j,k)$$ for which I know whether $$e_j > e_k$$, $$e_j = e_k$$, or $$e_j < e_k$$. There exists a pair $$(l,l+1)$$ that is missing from the set of comparisons. Is it ever possible, then, to prove that the sequence is sorted?

• A note in case anyone finds this page later with the question of whether you can verify a list is sorted without comparing anything; Only if you can put some limits on the inputs, and/or know something about the shape of the inputs; (e.g. radix sort). – HammerN'Songs May 10 '19 at 21:57
• There is, however, the possibility of optimizing the number of comparisons used in cases where it's not sorted. – Acccumulation May 10 '19 at 22:29
• @Acccumulation Is there actually such a possibility? Should be trivial to take any such program and cook up an adversarial list of length n that forces the program to do n-1 comparisons. See also A Killer Adversary for QuickSort, which takes this idea even further to forcing quicksort into the bad part of its asymptotic analysis. – Daniel Wagner May 11 '19 at 1:47
• @DanielWagner Yes, such optimization has to be done with respect to expected input of the particular application. – Acccumulation May 11 '19 at 17:35
• Probably not possible. But please clarify: did you mean that you only know the comparisons of the form (j,j+1), not general (j,k)? For example, do you ever know the comparison of two items of indices (j,j+3) ? – Ron May 11 '19 at 21:04

It is impossible. Suppose that you have the result of all comparisons except for the pair $$(i,i+1)$$. Then you wouldn't be able to distinguish between the following two cases: $$1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\ 1,2,\ldots,i-1,i+1,i,i+2,\ldots,n$$