A classificação de uma lista pode ser verificada sem comparar os vizinhos?

Uma lista de itens $n$ pode ser verificada conforme classificada, comparando cada item ao seu vizinho. No meu aplicativo, não poderei comparar todos os itens com seus vizinhos: em vez disso, as comparações às vezes serão entre elementos distantes. Dado que a lista contém mais de três itens e também que a comparação é a única operação suportada, já existe uma "rede" de comparações que provam que a lista está classificada, mas falta pelo menos um vizinho direto para vizinho comparação?

Formalmente, por uma sequência de elementos $e_i$ , I tem um conjunto de pares de índices $(j,k)$ para os quais se conhecem eu $e_j > e_k$ , $e_j = e_k$ , ou $e_j < e_k$ . Existe um par $(l,l+1)$ que está faltando no conjunto de comparações. É sempre possível, então, provar que a sequência está classificada?

$(i,i+1)$