Ordenar por Comparação: o Limite, a Biblioteca e a Seleção

Quase toda solução de competição chama std::sort em algum lugar. Isso não quer dizer que a ordenação esteja entendida. Quer dizer apenas que todos sabem onde fica o botão. Este artigo trata do botão, do mecanismo por trás dele e dos momentos em que apertá-lo é exatamente a coisa errada a fazer.

O Artigo 9 tratou a busca como compra de informação: cada comparação descarta metade da incerteza. A ordenação é a outra metade do negócio. Ela paga $O(n\log n)$ uma única vez para que muitas perguntas futuras fiquem baratas, e essa conta tem um piso que nenhum algoritmo baseado em comparações consegue furar. O percurso começa por esse piso, passa pela maneira como a biblioteca do MSVC se aproxima dele, pelas regras que uma comparação precisa respeitar, pela estabilidade e termina na seleção, a ferramenta para quando ordenar tudo é pagar demais.

As medições foram feitas com o MSVC do Visual Studio 18.10.3, com /std:c++latest /O2, em um Intel Core i7-10750H. Cada tempo é a mediana de cinco execuções depois de uma de aquecimento, e cada execução ordena uma cópia nova dos mesmos dados, feita fora do cronômetro.

1. O limite inferior

A ordenação por comparação tem um limite inferior de $\mathrm{\Omega }(n\log n)$ comparações. Isso não é uma limitação de std::sort. É uma limitação de informação.

Imagine ordenar $n$ elementos distintos usando apenas perguntas da forma $a$ é menor que $b$?. Há $n!$ ordens possíveis para os elementos de entrada, e o algoritmo precisa terminar sabendo qual delas é a verdadeira, porque cada ordem exige uma sequência diferente de movimentos para ser desfeita. Todo algoritmo desse tipo pode ser desenhado como uma árvore de decisão: cada nó interno é uma comparação, cada ramo é uma das duas respostas e cada folha é uma ordem final. A Figura 1 mostra uma árvore para três elementos.