Fusão em tempo linear

A parte restante da ordenação por intercalação é a função merge, a qual intercala dois subarrays adjacentes que estão ordenados, array[p..q] e array[q+1..r] em um único subarray ordenado em array[p..r]. Vamos ver como construir essa função de forma que seja o mais eficiente possível. Vamos dizer que os dois subarrays têm um total de $n$‍ elementos. Temos que examinar cada um dos elementos a fim de intercalá-los no mesmo array, então o melhor que podemos esperar seria um tempo de intercalação de $\mathrm{\Theta }(n)$‍. De fato, vamos ver como intercalar um total de $n$‍ elementos em um tempo $\mathrm{\Theta }(n)$‍.

Para intercalar os subarrays ordenados array[p..q] e array[q+1..r] e ter o resultado array[p..r], precisamos primeiro criar arrays temporários e copiar array[p..q] e array[q+1..r] nesses arrays temporários. Nós não podemos reescrever as posições em array[p..r] até que tenhamos copiados os elementos que estavam originalmente em array[p..q] e array[q+1..r] com segurança.

Portanto, a primeira tarefa da função merge é alocar dois arrays temporários, lowHalf e highHalf, para copiar todos os elementos de array[p..q] para lowHalf, e todos os elementos de array[q+1..r] para highHalf. Quão grande deve ser lowHalf? O subarray array[p..q] contém $q-p+1$‍ elementos. E highHalf? O subarray array[q+1..r] contém $r-q$‍ elementos. (Em JavaScript, nós não temos que especificar o tamanho de um array quando o criamos, mas como nós temos que fazer isso em muitas outras linguagens, nós frequentemente levamos isso em conta quando estamos descrevendo o algoritmo.)

No nosso array de exemplo [14, 7, 3, 12, 9, 11, 6, 2], é assim que as coisas vão estar depois de termos ordenado recursivamente os arrays array[0..3] e array[4..7] (de forma que $p=0$‍, $q=3$‍, e $r=7$‍) e copiado esses subarrays para lowHalf e highHalf:

Os números em array estão cinza para indicar que ainda que essas posições de array contenham valores, os valores "reais" agora estão em lowHalf e highHalf. Podemos sobrescrever os números cinza à vontade.

Em seguida, nós mesclamos os dois arrays ordenados, agora em lowHalf e highHalf, de volta para array[p..r]. Deveríamos colocar o menor valor dos dois subarrays em array[p]. Onde o menor valor poderia estar? Como os subarrays estão ordenados, o menor valor deve estar em um desses dois locais: ou em lowHalf[0] ou em highHalf[0]. (É possível que haja o mesmo valor no dois locais, nesse caso podemos considerar qualquer um dos dois o menor valor.) Com apenas uma comparação, podemos decidir entre copiar lowHalf[0] ou highHalf[0] para o array[p]. Em nosso exemplo, highHalf[0] era menor. Vamos estabelecer também três variáveis para indexar os arrays:

Depois de copiarmos de lowHalf ou highHalf para array, devemos incrementar (adicionar 1 a) k de forma a copiar o próximo menor elemento na próxima posição de array. Também temos que incrementar i se copiamos de lowHalf, ou incrementar j se copiamos de highHalf. A seguir estão as representações dos arrays antes e depois do primeiro elemento ser copiado para array:

Nós deixamos highHalf[0] cinza para indicar que ele contém um valor que nós não vamos mais considerar. A parte do array highHalf que ainda não foi intercalada começa no índice j, que agora é 1. O valor em array[p] não está mais cinza porque nós copiamos um valor "real" para esse campo.

Onde o próximo valor a ser copiado de volta para array deve estar? Ele deve ser o primeiro elemento ainda não copiado de volta em lowHalf (lowHalf[0]) ou em highHalf (highHalf[1]). Com uma comparação nós determinamos que lowHalf[0] é menor, e então o copiamos para array[k] e incrementamos k e i:

Em seguida, comparamos lowHalf[1] e highHalf[1], e determinamos que devemos copiar highHalf[1] para array[k]. E então incrementamos k e j:

Continuando, sempre comparando lowHalf[i] e highHalf[j], copiando o menor dos dois para array[k], e incrementando i ou j:

Em algum momento, todos os elementos de lowHalf ou de highHalf serão copiados de volta para array. Nesse exemplo, todos os elementos de highHalf são copiados de volta antes de alguns elementos de lowHalf terem sido copiados. Em casos assim, nós finalizamos apenas copiando os elementos restantes de up lowHalf ou de highHalf:

Nós dissemos que intercalar $n$‍ elementos leva um tempo $\mathrm{\Theta }(n)$‍, e portanto o tempo de execução da intercalação é linear em relação ao tamanho do subarray. Vamos verificar porque isso é verdade. Nós vimos três partes da intercalação:

Quantas linhas de código nós precisamos executar para cada um desses passos? É um número constante por elemento. Cada elemento é copiado de array para lowHalf ou highHalf exatamente uma vez no passo 1. Cada comparação no passo 2 leva um tempo constante, já que compara apenas dois elementos, e cada elemento "vence" no máximo uma vez. Cada elemento é copiado de volta para array exatamente uma vez nos passos 2 e 3 combinados. Como nós executamos cada linha de código um número constante de vezes por elemento e assumimos que o subarray array[p..q] contém $n$‍ elementos, o tempo de execução para intercalar é, de fato, $\mathrm{\Theta }(n)$‍.

No próximo desafio, você irá implementar esta operação de intercalação de tempo linear. Combinado os dois desafios, você terá implementado o algoritmo merge sort por completo.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.