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.

def mergeSort(alist):

    print("Splitting ",alist)

    if len(alist)>1:

        mid = len(alist)//2

        lefthalf = alist[:mid]

        righthalf = alist[mid:]

​

        mergeSort(lefthalf)

        mergeSort(righthalf)

​

        i=0

        j=0

        k=0

        while i < len(lefthalf) and j < len(righthalf):

            if lefthalf[i] < righthalf[j]:

                alist[k]=lefthalf[i]

                i=i+1

            else:

                alist[k]=righthalf[j]

                j=j+1

            k=k+1

​

        while i < len(lefthalf):

            alist[k]=lefthalf[i]

            i=i+1

            k=k+1

​

        while j < len(righthalf):

            alist[k]=righthalf[j]

            j=j+1

            k=k+1

    print("Merging ",alist)

​

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

​

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.