Merge Sort

Definição

O Merge Sort é um algoritmo de ordenação baseado na técnica de dividir e conquistar (divide and conquer). Ele divide a lista original em sublistas menores até que cada uma tenha um único elemento, e então intercala essas sublistas de forma ordenada para reconstruir a lista final.

É um algoritmo eficiente e com desempenho previsível.

Por que usar

Garante desempenho consistente: O(n log n) no pior caso;
Preserva a ordem de elementos iguais (estável);
Ideal para ordenar grandes volumes de dados ou listas ligadas;
Facilmente adaptável para programação funcional e paralelismo.

Complexidade

Caso	Tempo
Melhor caso	O(n log n)
Médio caso	O(n log n)
Pior caso	O(n log n)

Estável? Sim
Espaço adicional: O(n)

(Um algoritmo de ordenação é estável quando mantém a ordem original de elementos iguais após a ordenação.)

Exemplo prático (Python)

def merge_sort(lista):
    if len(lista) <= 1:
        return lista

    meio = len(lista) // 2
    esquerda = merge_sort(lista[:meio])
    direita = merge_sort(lista[meio:])
    return intercalar(esquerda, direita)

def intercalar(esq, dir):
    resultado = []
    i = j = 0

    while i < len(esq) and j < len(dir):
        if esq[i] < dir[j]:
            resultado.append(esq[i])
            i += 1
        else:
            resultado.append(dir[j])
            j += 1

    resultado.extend(esq[i:])
    resultado.extend(dir[j:])
    return resultado

# Exemplo
numeros = [5, 3, 8, 1, 2]
ordenados = merge_sort(numeros)
print(ordenados)  # [1, 2, 3, 5, 8]

Visualização do processo

Dada a lista: [5, 3, 8, 1, 2]

Divide: [5, 3] e [8, 1, 2]
Divide mais: [5] [3] [8] [1] [2]

Intercalação:

[5] + [3] → [3, 5]
[1] + [2] → [1, 2]
[1, 2] + [8] → [1, 2, 8]

Intercala final:

[3, 5] + [1, 2, 8] → [1, 2, 3, 5, 8]