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

O Melhor dos Dois Mundos: Entendendo a Complexidade O(N log N) do Merge Sort 🥇

Nos posts anteriores, conquistamos a velocidade da Busca Binária O(log N) e a eficiência Linear O(N). Agora, vamos ao padrão-ouro para o 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 ela combina o poder de dividir o problema log N com a eficiência de processar os resultados de forma linear N.

---

A Lógica do Merge Sort: Divisão e Mesclagem

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

1. Fase de Divisão (log N) 🌳

O algoritmo divide recursivamente a lista em metades, continuando a divisão até que restem apenas listas de um único elemento (que, por definição, estão ordenadas).

• Se você tem 1.000.000 de itens, você só precisa de 20 divisões (log_2 1.000.000 ≈ 20) para chegar ao caso base.
• O log N é a altura da árvore de recursão.

2. Fase de Mesclagem N 🔗

É aqui que o trabalho pesado é feito. Em cada nível da recursão (os log N níveis), o algoritmo mescla (combina) as listas ordenadas de volta em uma única lista maior e também ordenada.

• Para mesclar duas listas que, juntas, somam N elementos, o algoritmo precisa fazer, no máximo, N comparações para garantir que a saída esteja em ordem.
• Esta operação de mesclagem é intrinsecamente O(N) (Linear).

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

---

O Coração 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 (++) e trabalhar apenas nas cabeças das listas.

Nosso código de mesclagem faz exatamente isso, comparando as cabeças (h_a e h_b) e movendo o menor elemento para o resultado recursivamente.

# --- 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

Código Final: O Merge Sort Completo

Este código encapsula a filosofia O(N log N):

defmodule MergeSort do
  @doc "Implementação do Merge Sort em Elixir (O(N log N))."
  def sort(list) do
    case list do
      [] -> []; [_] -> list # Caso Base
      _ ->
        # 1. DIVISÃO: Agora a função está definida.
        {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

 # Adicionar o código da acima
end

Análise: 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óxima Parada: O Desafio Final

No próximo e último post da série, faremos uma aplicação avançada do O(N). Veremos como usar a técnica dos Dois Ponteiros para resolver o problema Squares of a Sorted Array (que já exploramos), transformando a necessidade de uma ordenação O(N log N) final em um único e elegante passo O(N)! Além disso, revelaremos o segredo do O(1) dos Mapas de Elixir (a estrutura HAMT).