5.11. O Merge Sort¶

Agora nós voltamos nossa atenção para usar a estratégia de “dividir para conquistar” como uma forma de melhorar o desempenho dos algoritmos de ordenação. O primeiro algoritmo que iremos estudar é o merge sort, um algoritmo recursivo que divide uma lista continuamente pela metade. Se a lista estiver vazia ou tiver um único item, ela está ordenada por definição (o caso base). Se a lista tiver mais de um item, dividimos a lista e invocamos recursivamente um merge sort em ambas as metades. Assim que as metades estiverem ordenadas, a operação fundamental, chamada de intercalação, é realizada. Intercalar é o processo de pegar duas listas menores ordenadas e combiná-las de modo a formar uma lista nova, única e ordenada. A Figura 10 mostra nossa lista familiar sendo dividida pelo mergeSort. A Figura 11 mostra como as listas mais simples, agora ordenadas, são intercaladas.

Figura 10: Dividindo a Lista no Merge Sort¶

Figura 11: Intercalação das Listas¶

A função mergeSort mostrada em ActiveCode 1 começa perguntando pelo caso base. Se o tamanho da lista form menor ou igual a um, então já temos uma lista ordenada e nenhum processamento adicional é necessário. Se, por outro lado, o tamanho da lista for maior do que um, então usamos a operação de slice do Python para extrair a metades esquerda e direita. É importante observar que a lista pode não ter um número par de elementos. Isso, contudo, não importa, já que a diferença de tamanho entre as listas será de apenas um elemento.

Quando a função mergeSort é chamada nas metades esquerda e direita (linhas 8-9), pressupõe-se que elas já estão ordenadas. O resto da função (linhas 11-31) é responsável por intercalar as duas listas ordenadas menores em uma lista ordenada maior. Note que a operação de intercalação coloca um item por vez de volta na lista original (alist) ao tomar repetidamente o menor item das listas ordenadas.

A função mergeSort foi aumentada com uma chamada de print (linha 2) para mostrar o conteúdo da lista sendo ordenada no começo de cada chamada. Também há uma declaração de print (linha 32) para mostrar o processo de intercalação. O transcrito abaixo mostra o resultado de executar a função na nossa lista de exemplo. Observe que a lista com 44, 55 e 20 não irá ser dividida igualmente. A primeira metade resulta em [44] enquanto a segunda em [55,20]. É fácil perceber que o procesos de divisão irá gerar em algum momento uma lista que poderá ser imediatamente intercalada com outras listas ordenadas.

Para analisar a função mergeSort, precisamos considerar os dois processos distintos que compõem sua implementação. Primeiro, a lista é dividida em duas metades. Nós já computamos (na busca binária) que podemos dividir uma lista ao meio \(\log n\) vezes, onde n é o tamanho da lista. O segundo processo é a intercalação. Cada item na lista irá ser processado em algum momento e colocado na lista ordenada. Então a operação de intercalação que resulta em uma lista de tamanho n requer n operações. O resultado desta análise é: \(\log n\) divisões, cada qual custando \(n\), totalizando \(n\log n\) operações. Logo, o merge sort é um algoritmo \(O(n\log n)\).

Lembre-se de que o operador “slice” é \(O(k)\), onde k é o tamanho do corte. Para garantir que a função mergeSort seja \(O(n\log n)\), precisamos remover o operador “slice”. Isso é possível se simplesmente passarmos os índices de início e fim junto com a lista quando fazemos a chamada recursiva. Deixamos essa implementação como um exercício.

É importante notar que a função mergeSort requer espaço extra para armazenar as duas metades conforme elas são extraídas no processo de divisão. Esse espaço adicional pode ser um fator crítico se a lista for grande e pode tornar a ordenação problemática em conjuntos grandes de dados.