Merge Sort em Rust | Rust Brasil

O Merge Sort (ordenação por intercalação) é um algoritmo de ordenação baseado na estratégia de divisão e conquista. Ele divide o vetor ao meio recursivamente até obter subvetores de tamanho 1 (que são trivialmente ordenados), e então intercala (merge) os subvetores ordenados para produzir o resultado final. Foi inventado por John von Neumann em 1945 e permanece como um dos algoritmos de ordenação mais importantes da computação.

O Merge Sort garante complexidade O(n log n) em todos os casos — melhor, médio e pior — o que o torna previsível e confiável. Ele também é estável, preservando a ordem relativa de elementos iguais. Sua principal desvantagem é o uso de O(n) de memória extra para a intercalação. O Merge Sort é a base de algoritmos profissionais como o TimSort, usado em Python, Java e no sort() estável do Rust.

Como Funciona

O algoritmo segue três etapas:

Dividir: divide o vetor ao meio recursivamente.
Conquistar: quando os subvetores têm tamanho 1, estão ordenados.
Combinar (merge): intercala dois subvetores ordenados em um único vetor ordenado.

Vetor inicial: [38, 27, 43, 3, 9, 82, 10]

=== FASE DE DIVISÃO ===

                    [38, 27, 43, 3, 9, 82, 10]
                   /                            \
          [38, 27, 43, 3]                [9, 82, 10]
          /              \               /          \
      [38, 27]        [43, 3]       [9, 82]       [10]
      /      \        /      \      /      \        |
   [38]    [27]    [43]     [3]  [9]     [82]     [10]

=== FASE DE INTERCALAÇÃO (MERGE) ===

   [38]    [27]    [43]     [3]  [9]     [82]     [10]
      \      /        \      /      \      /        |
      [27, 38]        [3, 43]       [9, 82]       [10]
          \              /               \          /
          [3, 27, 38, 43]                [9, 10, 82]
                   \                            /
                    [3, 9, 10, 27, 38, 43, 82]

Detalhamento da operação de merge (intercalação) de [3, 27, 38, 43] e [9, 10, 82]:

Esquerda: [3, 27, 38, 43]    Direita: [9, 10, 82]    Resultado: []
           ^                           ^

Passo 1: 3 < 9  → pega 3    Resultado: [3]
              ^                ^
Passo 2: 27 > 9 → pega 9    Resultado: [3, 9]
              ^                   ^
Passo 3: 27 > 10 → pega 10  Resultado: [3, 9, 10]
              ^                       ^
Passo 4: 27 < 82 → pega 27  Resultado: [3, 9, 10, 27]
                 ^                    ^
Passo 5: 38 < 82 → pega 38  Resultado: [3, 9, 10, 27, 38]
                    ^                 ^
Passo 6: 43 < 82 → pega 43  Resultado: [3, 9, 10, 27, 38, 43]
                       (fim)          ^
Passo 7: copia restante 82  Resultado: [3, 9, 10, 27, 38, 43, 82]

Complexidade

Caso	Tempo	Espaço
Melhor	O(n log n)	O(n)
Médio	O(n log n)	O(n)
Pior	O(n log n)	O(n)

Tempo O(n log n) em todos os casos: a divisão gera log n níveis, e cada nível faz O(n) trabalho de intercalação. Diferente do Quick Sort, o Merge Sort nunca degrada para O(n²).
Espaço O(n): necessita de um vetor auxiliar do mesmo tamanho para a intercalação. Esta é a principal desvantagem em relação a algoritmos in-place.
Estabilidade: durante a intercalação, quando dois elementos são iguais, o da esquerda é escolhido primeiro, preservando a ordem original.

A profundidade da recursão é O(log n), resultando em O(log n) de espaço extra na pilha de chamadas.

Implementação em Rust

Versão Recursiva (Top-Down)

/// Merge Sort recursivo (top-down).
/// Retorna um novo Vec ordenado, sem modificar o original.
fn merge_sort<T: PartialOrd + Clone>(vetor: &[T]) -> Vec<T> {
    let n = vetor.len();

    // Caso base: vetor de 0 ou 1 elemento já está ordenado
    if n <= 1 {
        return vetor.to_vec();
    }

    // Dividir ao meio
    let meio = n / 2;
    let esquerda = merge_sort(&vetor[..meio]);
    let direita = merge_sort(&vetor[meio..]);

    // Intercalar as duas metades ordenadas
    merge(&esquerda, &direita)
}

/// Intercala dois slices ordenados em um novo Vec ordenado.
fn merge<T: PartialOrd + Clone>(esquerda: &[T], direita: &[T]) -> Vec<T> {
    let mut resultado = Vec::with_capacity(esquerda.len() + direita.len());
    let mut i = 0; // índice da esquerda
    let mut j = 0; // índice da direita

    // Comparar elementos de ambos os lados e adicionar o menor
    while i < esquerda.len() && j < direita.len() {
        if esquerda[i] <= direita[j] {
            resultado.push(esquerda[i].clone());
            i += 1;
        } else {
            resultado.push(direita[j].clone());
            j += 1;
        }
    }

    // Copiar elementos restantes
    while i < esquerda.len() {
        resultado.push(esquerda[i].clone());
        i += 1;
    }
    while j < direita.len() {
        resultado.push(direita[j].clone());
        j += 1;
    }

    resultado
}

fn main() {
    let numeros = vec![38, 27, 43, 3, 9, 82, 10];
    println!("Antes:  {:?}", numeros);
    let ordenado = merge_sort(&numeros);
    println!("Depois: {:?}", ordenado);

    let palavras = vec!["rust", "python", "go", "java", "c"];
    println!("\nAntes:  {:?}", palavras);
    let ordenado = merge_sort(&palavras);
    println!("Depois: {:?}", ordenado);
}

Versão In-Place (com buffer auxiliar)

/// Merge Sort in-place que modifica o slice diretamente.
/// Usa um buffer auxiliar para a intercalação.
fn merge_sort_in_place<T: PartialOrd + Clone + Default>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }

    let meio = n / 2;
    merge_sort_in_place(&mut vetor[..meio]);
    merge_sort_in_place(&mut vetor[meio..]);

    // Intercalar usando buffer temporário
    let esquerda: Vec<T> = vetor[..meio].to_vec();
    let direita: Vec<T> = vetor[meio..].to_vec();

    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < esquerda.len() && j < direita.len() {
        if esquerda[i] <= direita[j] {
            vetor[k] = esquerda[i].clone();
            i += 1;
        } else {
            vetor[k] = direita[j].clone();
            j += 1;
        }
        k += 1;
    }

    while i < esquerda.len() {
        vetor[k] = esquerda[i].clone();
        i += 1;
        k += 1;
    }

    while j < direita.len() {
        vetor[k] = direita[j].clone();
        j += 1;
        k += 1;
    }
}

fn main() {
    let mut v = vec![38, 27, 43, 3, 9, 82, 10];
    println!("Antes:  {:?}", v);
    merge_sort_in_place(&mut v);
    println!("Depois: {:?}", v);
}

Exemplo de Execução

Antes:  [38, 27, 43, 3, 9, 82, 10]
Depois: [3, 9, 10, 27, 38, 43, 82]

Antes:  ["rust", "python", "go", "java", "c"]
Depois: ["c", "go", "java", "python", "rust"]

Versão com rastreamento da recursão:

fn merge_sort_rastreado(vetor: &[i32], nivel: usize) -> Vec<i32> {
    let prefixo = "  ".repeat(nivel);
    println!("{}merge_sort({:?})", prefixo, vetor);

    if vetor.len() <= 1 {
        println!("{}  → base: {:?}", prefixo, vetor);
        return vetor.to_vec();
    }

    let meio = vetor.len() / 2;
    let esquerda = merge_sort_rastreado(&vetor[..meio], nivel + 1);
    let direita = merge_sort_rastreado(&vetor[meio..], nivel + 1);

    let mut resultado = Vec::with_capacity(esquerda.len() + direita.len());
    let (mut i, mut j) = (0, 0);

    while i < esquerda.len() && j < direita.len() {
        if esquerda[i] <= direita[j] {
            resultado.push(esquerda[i]);
            i += 1;
        } else {
            resultado.push(direita[j]);
            j += 1;
        }
    }
    resultado.extend_from_slice(&esquerda[i..]);
    resultado.extend_from_slice(&direita[j..]);

    println!("{}  → merge({:?}, {:?}) = {:?}", prefixo, esquerda, direita, resultado);
    resultado
}

fn main() {
    let v = vec![38, 27, 43, 3];
    println!("Entrada: {:?}\n", v);
    let resultado = merge_sort_rastreado(&v, 0);
    println!("\nResultado: {:?}", resultado);
}

Variações e Otimizações

1. Merge Sort Iterativo (Bottom-Up)

Em vez de dividir recursivamente, o bottom-up começa intercalando pares de 1 elemento, depois pares de 2, depois de 4, e assim por diante. Elimina o overhead da recursão.

/// Merge Sort iterativo (bottom-up).
/// Evita a recursão, usando iteração com tamanho de bloco crescente.
fn merge_sort_bottom_up<T: PartialOrd + Clone>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }

    let mut buffer = vetor.to_vec();
    let mut tamanho = 1; // tamanho dos blocos a serem intercalados

    while tamanho < n {
        let mut inicio = 0;

        while inicio < n {
            let meio = (inicio + tamanho).min(n);
            let fim = (inicio + 2 * tamanho).min(n);

            // Intercalar vetor[inicio..meio] com vetor[meio..fim]
            let mut i = inicio;
            let mut j = meio;
            let mut k = inicio;

            while i < meio && j < fim {
                if vetor[i] <= vetor[j] {
                    buffer[k] = vetor[i].clone();
                    i += 1;
                } else {
                    buffer[k] = vetor[j].clone();
                    j += 1;
                }
                k += 1;
            }

            while i < meio {
                buffer[k] = vetor[i].clone();
                i += 1;
                k += 1;
            }

            while j < fim {
                buffer[k] = vetor[j].clone();
                j += 1;
                k += 1;
            }

            inicio += 2 * tamanho;
        }

        // Copiar buffer de volta para o vetor
        vetor.clone_from_slice(&buffer);
        tamanho *= 2;
    }
}

fn main() {
    let mut v = vec![38, 27, 43, 3, 9, 82, 10];
    println!("Antes:  {:?}", v);
    merge_sort_bottom_up(&mut v);
    println!("Depois: {:?}", v);
}

Visualização do bottom-up:

Vetor: [38, 27, 43, 3, 9, 82, 10]

Tamanho 1: merge pares adjacentes
  merge([38], [27]) → [27, 38]
  merge([43], [3])  → [3, 43]
  merge([9], [82])  → [9, 82]
  [10] sozinho       → [10]
  Resultado: [27, 38, 3, 43, 9, 82, 10]

Tamanho 2: merge blocos de 2
  merge([27, 38], [3, 43])  → [3, 27, 38, 43]
  merge([9, 82], [10])      → [9, 10, 82]
  Resultado: [3, 27, 38, 43, 9, 10, 82]

Tamanho 4: merge blocos de 4
  merge([3, 27, 38, 43], [9, 10, 82]) → [3, 9, 10, 27, 38, 43, 82]

Final: [3, 9, 10, 27, 38, 43, 82]

2. Merge Sort com Otimização de Insertion Sort

Para subvetores pequenos, o Insertion Sort é mais rápido que continuar dividindo. Usamos um limiar para trocar de estratégia:

/// Merge Sort otimizado: usa Insertion Sort para partições pequenas.
const LIMIAR: usize = 16;

fn merge_sort_otimizado<T: PartialOrd + Clone>(vetor: &[T]) -> Vec<T> {
    let n = vetor.len();

    if n <= LIMIAR {
        // Usar Insertion Sort para partições pequenas
        let mut resultado = vetor.to_vec();
        for i in 1..resultado.len() {
            let mut j = i;
            while j > 0 && resultado[j - 1] > resultado[j] {
                resultado.swap(j - 1, j);
                j -= 1;
            }
        }
        return resultado;
    }

    let meio = n / 2;
    let esquerda = merge_sort_otimizado(&vetor[..meio]);
    let direita = merge_sort_otimizado(&vetor[meio..]);

    // Otimização: se já está ordenado, não precisa intercalar
    if esquerda.last() <= direita.first() {
        let mut resultado = esquerda;
        resultado.extend(direita);
        return resultado;
    }

    merge_vecs(&esquerda, &direita)
}

fn merge_vecs<T: PartialOrd + Clone>(esquerda: &[T], direita: &[T]) -> Vec<T> {
    let mut resultado = Vec::with_capacity(esquerda.len() + direita.len());
    let (mut i, mut j) = (0, 0);

    while i < esquerda.len() && j < direita.len() {
        if esquerda[i] <= direita[j] {
            resultado.push(esquerda[i].clone());
            i += 1;
        } else {
            resultado.push(direita[j].clone());
            j += 1;
        }
    }
    resultado.extend_from_slice(&esquerda[i..]);
    resultado.extend_from_slice(&direita[j..]);
    resultado
}

fn main() {
    let v = vec![38, 27, 43, 3, 9, 82, 10, 15, 7, 1, 45, 22];
    println!("Antes:  {:?}", v);
    let ordenado = merge_sort_otimizado(&v);
    println!("Depois: {:?}", ordenado);
}

3. Natural Merge Sort

Aproveita sequências já ordenadas (runs) no vetor original, em vez de sempre dividir ao meio:

/// Natural Merge Sort — detecta e aproveita sequências já ordenadas.
fn natural_merge_sort<T: PartialOrd + Clone>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }

    loop {
        // Encontrar todas as runs (sequências ordenadas)
        let mut runs: Vec<(usize, usize)> = Vec::new();
        let mut inicio = 0;

        while inicio < n {
            let mut fim = inicio + 1;
            while fim < n && vetor[fim - 1] <= vetor[fim] {
                fim += 1;
            }
            runs.push((inicio, fim));
            inicio = fim;
        }

        // Se há apenas uma run, o vetor está ordenado
        if runs.len() == 1 {
            break;
        }

        // Intercalar runs adjacentes
        let mut i = 0;
        while i + 1 < runs.len() {
            let (inicio_a, fim_a) = runs[i];
            let (_, fim_b) = runs[i + 1];

            // Intercalar vetor[inicio_a..fim_a] com vetor[fim_a..fim_b]
            let esquerda: Vec<T> = vetor[inicio_a..fim_a].to_vec();
            let direita: Vec<T> = vetor[fim_a..fim_b].to_vec();

            let mut ei = 0;
            let mut di = 0;
            let mut k = inicio_a;

            while ei < esquerda.len() && di < direita.len() {
                if esquerda[ei] <= direita[di] {
                    vetor[k] = esquerda[ei].clone();
                    ei += 1;
                } else {
                    vetor[k] = direita[di].clone();
                    di += 1;
                }
                k += 1;
            }
            while ei < esquerda.len() {
                vetor[k] = esquerda[ei].clone();
                ei += 1;
                k += 1;
            }
            while di < direita.len() {
                vetor[k] = direita[di].clone();
                di += 1;
                k += 1;
            }

            i += 2;
        }
    }
}

fn main() {
    // Vetor com sequências parcialmente ordenadas
    let mut v = vec![1, 3, 5, 2, 4, 6, 0, 7, 8];
    println!("Antes:  {:?}", v);
    natural_merge_sort(&mut v);
    println!("Depois: {:?}", v);
}

Quando Usar

O Merge Sort é a escolha ideal nos seguintes cenários:

Garantia de O(n log n): quando o pior caso não pode degradar, o Merge Sort é a escolha segura. Diferente do Quick Sort, nunca cai para O(n²).
Estabilidade necessária: para preservar a ordem relativa de elementos iguais (ex: ordenar registros por um campo sem perder a ordenação por outro campo).
Ordenação externa (external sort): para dados maiores que a memória RAM, o Merge Sort é naturalmente adaptável — basta intercalar blocos lidos do disco.
Listas ligadas: o Merge Sort é especialmente eficiente para listas ligadas, pois a intercalação pode ser feita sem memória extra.
Paralelismo: as duas metades podem ser ordenadas independentemente em threads separadas.

Evite o Merge Sort quando:

Memória extra O(n) for proibitiva — considere Heap Sort (in-place, O(n log n)) ou Quick Sort.
O vetor for pequeno (n < 50) — o Insertion Sort é mais rápido.

Comparação com Outros Algoritmos

Característica	Merge Sort	Quick Sort	Heap Sort	Insertion Sort
Tempo (médio)	O(n log n)	O(n log n)	O(n log n)	O(n²)
Tempo (pior)	O(n log n) ✓	O(n²)	O(n log n) ✓	O(n²)
Espaço	O(n)	O(log n) ✓	O(1) ✓	O(1) ✓
Estável	Sim ✓	Não	Não	Sim ✓
Cache-friendly	Não	Sim ✓	Não	Sim ✓
Paralelizável	Sim ✓	Sim	Não	Não
Externo	Sim ✓	Não	Não	Não

Na prática, o Quick Sort costuma ser mais rápido que o Merge Sort em vetores na memória devido ao melhor padrão de acesso ao cache. No entanto, o Merge Sort é imbatível para ordenação estável, ordenação externa e quando a garantia de O(n log n) é necessária.

Exercícios Práticos

Contagem de inversões com Merge Sort: Modifique o Merge Sort para contar o número de inversões no vetor durante a intercalação. Quando direita[j] < esquerda[i], todos os elementos esquerda[i..meio] formam inversões com direita[j]. Implemente e teste.
Merge Sort paralelo: Use std::thread para ordenar as duas metades em threads separadas. Compare o tempo de execução com a versão sequencial para vetores de 1 milhão de elementos. Qual é o speedup obtido?
K-way merge: Implemente uma função que intercala k vetores ordenados em um único vetor ordenado. Use uma abordagem de intercalação em árvore (merge pairs até restar 1). Qual é a complexidade?
Merge Sort para arquivos: Simule a ordenação externa: divida um vetor grande em “blocos” de tamanho fixo, ordene cada bloco com Insertion Sort, e depois use merge para intercalar todos os blocos. Compare o número de operações com o Merge Sort padrão.

Veja Também

Quick Sort em Rust — alternativa in-place, geralmente mais rápido na prática
Heap Sort em Rust — in-place com O(n log n) garantido
Insertion Sort em Rust — usado como caso base para partições pequenas
Vec — Vetores Dinâmicos — alocação e manipulação de vetores
Slice — Fatias de Memória — divisão de slices com split_at()
Iterator — Iteradores — chain(), zip() e operações funcionais
Otimização de Performance em Rust — técnicas avançadas de performance