Como funciona o merge sort?

Question

Accepted Answer

**Merge sort** é um algoritmo **divide-and-conquer**, **estável** que funciona em tempo garantido **O(n log n)**. Ele divide o array ao meio, ordena cada metade recursivamente, e então mescla as duas metades ordenadas.

## A ideia

Um elemento único já está ordenado (caso base). Mesclar duas listas ordenadas é linear, e fazemos log n níveis de mesclagem.

## Exemplo

```python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # sort left half
    right = merge_sort(arr[mid:])     # sort right half
    return merge(left, right)

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:              # <= keeps it stable
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:]); result.extend(b[j:])
    return result

merge_sort([5, 2, 4, 1, 3])           # -> [1, 2, 3, 4, 5]
```

## Complexidade

- **Tempo:** O(n log n) em *todos* os casos (melhor, médio, pior).
- **Espaço:** O(n) para os buffers de mesclagem (não in-place).

## Quando usar / armadilhas

Ideal quando você precisa de **estabilidade** ou O(n log n) garantido, e para **listas ligadas** e **ordenação externa** de arquivos enormes. A memória extra O(n) é sua principal desvantagem.

## Por que isso importa

Merge sort garante O(n log n) independentemente da entrada, diferentemente do caso pior O(n²) do quicksort.

Sua estabilidade preserva a ordem relativa de chaves iguais, o que é importante para ordenação de múltiplas chaves.

O passo de mesclagem é uma primitiva reutilizável, e a estrutura divide-and-conquer é um padrão que você reutilizará em todo lugar.