Ordenar uma lista é uma das tarefas que os computadores mais fazem: nomes num cadastro, preços numa busca, resultados de uma eleição. Em 1945, quando o EDVAC ainda estava no papel, von Neumann quis mostrar que a máquina do seu relatório servia para trabalhos que não eram só contas, e escreveu à mão um programa para ordenar e intercalar listas. É um dos primeiros programas escritos para um computador de programa armazenado, e o método que ele usou, hoje chamado de merge sort, ainda é um dos mais usados.

Juntar duas listas ordenadas

O passo básico é intercalar (merge) duas listas que já estão em ordem. Basta olhar os primeiros elementos de cada uma, tirar o menor e repetir:

$$[2, 5, 9] \text{ e } [3, 4, 10] \;\longrightarrow\; [2, 3, 4, 5, 9, 10].$$

Cada comparação coloca um número no lugar certo. Para juntar duas listas com um total de $n$ elementos, bastam no máximo $n - 1$ comparações.

Animação do merge sort: os números são separados em grupos menores e reunidos em ordem. A fusão escolhe, a cada passo, o menor entre os primeiros elementos ainda disponíveis das duas listas.
Animação do merge sort: os números são separados em grupos menores e reunidos em ordem. A fusão escolhe, a cada passo, o menor entre os primeiros elementos ainda disponíveis das duas listas.Swfung8 · Wikimedia Commons · CC BY-SA 3.0

Dividir para conquistar

Para ordenar uma lista qualquer, von Neumann a dividiu em blocos de 1 elemento (que já estão ordenados!), intercalou os vizinhos em blocos de 2, depois de 4, de 8, e assim por diante:

Com $n = 2^k$ elementos, são $k = \log_2 n$ rodadas, e cada rodada faz no máximo $n$ comparações. O total é no máximo

$$n \log_2 n.$$

O método ingênuo, que procura o menor elemento, depois o segundo menor, e assim por diante, faz $\frac{n(n-1)}{2}$ comparações. Para $n = 16$, são $120$ contra no máximo $64$. Para um milhão de nomes, a diferença é entre cerca de 20 milhões de comparações e meio trilhão: segundos contra dias.

Exercício: conte as comparações

Intercale $[2, 5, 9]$ e $[3, 4, 10]$ contando as comparações.

$2$ vs $3$: sai o $2$. $5$ vs $3$: sai o $3$. $5$ vs $4$: sai o $4$. $5$ vs $10$: sai o $5$. $9$ vs $10$: sai o $9$. A primeira lista acabou, e o $10$ entra sem comparação. Foram $5$ comparações para $6$ elementos, dentro do limite de $n - 1 = 5$.

Exercício: mil e vinte e quatro elementos

Compare, para $n = 1024 = 2^{10}$, o número máximo de comparações do merge sort com o do método ingênuo.

Merge sort: $1024 \times 10 = 10\,240$. Ingênuo: $\frac{1024 \times 1023}{2} = 523\,776$. O merge sort faz cerca de $50$ vezes menos comparações, e a vantagem cresce com $n$.

Fontes: Donald E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching (1973) · Donald E. Knuth, “Von Neumann’s first computer program”, Computing Surveys (1970).

Todos os tópicos de John von Neumann · ← A arquitetura de von Neumann: o relatório do EDVAC · O método de Monte Carlo: calcular jogando dados →

Créditos das imagens.