MergeSort

A ideia por trás do Mergesort é simples. Para um vetor $A$ de $n$ números, execute os seguintes passos:

Divida o vetor em duas metades.
Ordene recursivamente cada metade.
Mescle as duas metades do vetor, isto é, combine as duas metades para formar um único arranjo.

A figura abaixo ilustra o funcionamento do Mergesort.

Ao repetir o procedimento de divisão do vetor em duas metades, chegará um ponto em que teremos vários vetores de um elemento apenas. Por definição um arranjo de um elemento já está ordenado. Neste momento, precisamos fazer a junção (merge) dos vetores. Começamos combinando dois a dois todos os vetores de tamanho um, formando vetores ordenados de tamanho dois. O mesmo se repete para vetores de tamanhos dois, três, quatro, e assim por diante. Uma coisa que pode não parecer óbvia a princípio (mas que ficará clara ao vermos a implementação do algoritmo) é que o trabalho pesado do mergesort é executado na etapa de merge, na qual dois sub-vetores ordenados são combinados em um único vetor ordenado.

Assim, a eficiência do Mergesort depende em quão eficientemente podemos combinar as duas metades ordenadas em um único arranjo ordenado. Podemos simplesmente concatenar as metades e então usar algum algoritmo de ordenação para ordenar o arranjo como um todo, ou então podemos combinar (mesclar, fazer o merge) das duas metades ordenadas em uma única sequência ordenada de forma eficiente. Mas como mesclar dois subvetores ordenados de forma eficiente? A ideia é mais ou menos a seguinte:

Seja $k$ o tamanho de cada um dos subvetores $V1$ e $V2$.
Crie um vetor auxiliar de tamanho $2k$.
Percorra os subvetores, sempre copiando para o vetor auxiliar o menor elemento na posição corrente dos subvetores, só avançando a posição no subvetor que teve o elemento copiado.

Com as ideias acima em mente, podemos implementar o Mergesort da seguinte forma:

def merge(A, aux, esquerda, meio, direita):
    """
    Combina dois vetores ordenados em um único vetor (também ordenado).
    """
    for k in range(esquerda, direita + 1):
        aux[k] = A[k]
    i = esquerda
    j = meio + 1
    for k in range(esquerda, direita + 1):
        if i > meio:
            A[k] = aux[j]
            j += 1
        elif j > direita:
            A[k] = aux[i]
            i += 1
        elif aux[j] < aux[i]:
            A[k] = aux[j]
            j += 1
        else:
            A[k] = aux[i]
            i += 1


def mergesort(A, aux, esquerda, direita):
    if direita <= esquerda:
        return
    meio = (esquerda + direita) // 2

    # Ordena a primeira metade do arranjo.
    mergesort(A, aux, esquerda, meio)

    # Ordena a segunda metade do arranjo.
    mergesort(A, aux, meio + 1, direita)

    # Combina as duas metades ordenadas anteriormente.
    merge(A, aux, esquerda, meio, direita)


# Testa o algoritmo.
A = random.sample(range(-10, 10), 10)
print("Arranjo não ordenado: ", A)
aux = [0] * len(A)
mergesort(A, aux, 0, len(A) - 1)
print("Arranjo ordenado:", A)

Arranjo não ordenado:  [0, 7, 8, 2, -2, 1, -5, 6, 3, -1]
Arranjo ordenado: [-5, -2, -1, 0, 1, 2, 3, 6, 7, 8]

Existem várias versões de implementações do mergesort. Para a implementação acima, nos baseamos na versão do professor Sedgewick.

No pior caso, o Mergesort possui complexidade $O(n \log n)$ no número de elementos do vetor de entrada, ele é um algoritmo estável, mas não é in-place, pois usa um vetor auxiliar para combinar os sub-vetores ordenados.

Note que a complexidade do Mergesort é inferior à dos algoritmos de ordenação por seleção e inserção. Na verdade, como veremos mais à frente, $O(n \log n)$ é a melhor complexidade que podemos obter para um algoritmo de ordenação genérico. O Bucketsort e o Radixsort possuem complexidade linear, mas não são algoritmos genéricos – eles só funcionam para entradas específicas.

Para entender por que o Mergesort possui complexidade $O(n \log n)$, precisamos analisar a complexidade dos dois procedimentos que o compõem:

mergesort: simplesmente divide o vetor de entrada em duas metades e invoca o procedimento merge. A divisão do vetor de entrada em dois possui complexidade logarítmica, pois o vetor original é dividido em duas metades $\log n$ vezes. Por exemplo, se o vetor de entrada possui tamanho 64, ele será dividido em vetores de tamanhos 32, 16, 8, 4, 2, e 1, ou seja, ele será dividido $6 = \log 64$ vezes.
merge: o procedimento merge possui complexidade $O(n)$. Entretanto, ele é executado $\log n$ vezes para um vetor de tamanho $n$. Assim, a complexidade final do Mergesort será $O(n \log n)$.

Exercícios

Faça o merge (combine) dois arranjos ordenados. Escreva um programa que tome como entrada dois arranjos ordenados de números inteiros e atualize o primeiro arranjo de modo a conter os elementos (ordenados) de ambos os arranjos. Assuma que o primeiro arranjo tem espaço o suficiente no final para acomodar os elementos de ambos os arranjos.

Clique para ver a solução

Sugestão de solução:

def combina_arranjos_ordenados(A, m, B, n):

    a, b, indice_escrita = m - 1, n - 1, m + n - 1
    while a >= 0 and b >= 0:
        if A[a] > B[b]:
            A[indice_escrita] = A[a]
            a -= 1
        else:
            A[indice_escrita] = B[b]
            b -= 1
        indice_escrita -= 1
    while b >= 0:
        A[indice_escrita] = B[b]
        indice_escrita, b = indice_escrita - 1, b - 1

Playground


			
				# Use este espaço para praticar o que você aprendeu nesta seção.
				
				# Basta digitar o código no espaço abaixo e clicar 'run'.