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. Faça o merge das duas metades.

Ao repetir o procedimento de divisão do vetor em duas metades, chegará um ponto em que teremos dois vetores de um elemento apenas, que por definição já estarão ordenados. Neste momento, precisamos fazer o merge dos dois vetores. 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 (fazer o merge) das duas metades ordenadas em uma única sequência ordenada de forma eficiente. Em uma implementação eficiente do Mergesort, a etapa de merge é feita com complexidade linear.

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

def merge(A, aux, esquerda, meio, direita):
    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
    mergesort(A, aux, esquerda, meio)
    mergesort(A, aux, meio + 1, direita)
    merge(A, aux, esquerda, meio, direita)

    
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: