MergeSort

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

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

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:

  1. Seja o tamanho de cada um dos subvetores e .
  2. Crie um vetor auxiliar de tamanho .
  3. 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 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, é 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 , precisamos analisar a complexidade dos dois procedimentos que o compõem: