O Padrão Ouro da Ordenação: O(N log N)

Contexto

Nos posts anteriores, conquistamos:

• Busca Binária – complexidade O(log N)
• Eficiência Linear – complexidade O(N)

Agora, vamos ao padrão‑ouro para ordenação: a complexidade O(N log N) (linearithmic).

Todo algoritmo de ordenação que precisa escalar para grandes volumes de dados (como Merge Sort ou Quick Sort) mira nessa complexidade, pois combina:

• o poder de dividir o problema (log N)
• a eficiência de processar os resultados de forma linear (N)

Como o Merge Sort atinge O(N log N)

O Merge Sort (Ordenação por Mesclagem) é um exemplo clássico de Divide and Conquer. Ele funciona em duas fases, que correspondem diretamente à sua complexidade O(N log N):

1. Divisão recursiva

   • O algoritmo divide a lista em metades até que restem listas de um único elemento (caso base).
   • Ex.: com 1 000 000 de itens são necessárias apenas ≈ 20 divisões (log₂ 1 000 000 ≈ 20).
   • O log N representa a altura da árvore de recursão.

2. Mesclagem

   • Em cada nível da recursão (há log N níveis) o algoritmo combina as listas ordenadas de volta em uma única lista maior e ordenada.
   • Para mesclar duas listas que, juntas, somam N elementos, são necessárias no máximo N comparações.
   • Essa operação é intrinsecamente O(N) (linear).

Como realizamos O(N) em cada um dos log N níveis, a complexidade total é O(N log N).

O(N) em Elixir: a função merge

A chave para um Merge Sort eficiente é garantir que a função de mesclagem seja rigorosamente O(N). Em Elixir, isso significa:

• nunca usar o operador de concatenação lenta (++)
• trabalhar apenas nas cabeças das listas

Código de mesclagem

## --- O CORAÇÃO O(N) DA MESCLAGEM ---

## Casos base para quando uma das listas se esgota:
defp merge([], list_b), do: list_b
defp merge(list_a, []), do: list_a

## Cláusula Recursiva Principal
defp merge([h_a | t_a] = list_a, [h_b | t_b] = list_b) do
  if h_a <= h_b do
    # h_a é menor: coloca na frente do resultado e continua a recursão
    # usando a cauda de A (t_a) e a lista B completa (list_b).
    [h_a | merge(t_a, list_b)]
  else
    # h_b é menor: coloca na frente do resultado e continua a recursão
    # usando a lista A completa (list_a) e a cauda de B (t_b).
    [h_b | merge(list_a, t_b)]
  end
end

Implementação completa do Merge Sort

defmodule MergeSort do
  @doc "Implementação do Merge Sort em Elixir (O(N log N))."
  def sort(list) do
    case list do
      [] -> []                     # Caso base
      [_] -> list                  # Caso base
      _ ->
        # 1. DIVISÃO
        {low, high} = split_list(list)

        # 2. RECURSÃO
        sorted_low  = sort(low)
        sorted_high = sort(high)

        # 3. MESCLAGEM
        merge(sorted_low, sorted_high)
    end
  end

  ## 🛠️ FUNÇÃO AUXILIAR DE DIVISÃO (Adicionada para corrigir o erro)
  # O(N) para encontrar o comprimento e dividir a lista ligada.
  defp split_list(list) do
    # Encontrar o ponto médio da lista
    len = length(list)
    split_point = trunc(len / 2)

    # Enum.split faz a divisão no ponto (O(N) por varrer a lista)
    Enum.split(list, split_point)
  end

  # Função de mesclagem (definida acima)
  defp merge([], list_b), do: list_b
  defp merge(list_a, []), do: list_a

  defp merge([h_a | t_a] = list_a, [h_b | t_b] = list_b) do
    if h_a <= h_b do
      [h_a | merge(t_a, list_b)]
    else
      [h_b | merge(list_a, t_b)]
    end
  end
end

Conclusão

O Merge Sort é o melhor que podemos fazer para ordenação genérica. Ele garante a performance O(N log N) em todos os casos (pior, médio e melhor), o que o torna incrivelmente estável e confiável.

Próximo post – Aplicação avançada do O(N): usaremos a técnica dos Dois Ponteiros para resolver o problema Squares of a Sorted Array, transformando a necessidade de uma ordenação O(N log N) em um único e elegante passo O(N). Também revelaremos o segredo do O(1) dos Mapas de Elixir (estrutura HAMT).