--- title: "Merge Sort em Rust" url: "https://rustlang.com.br/algoritmos/merge-sort/" markdown_url: "https://rustlang.com.br/algoritmos/merge-sort.MD" description: "Aprenda Merge Sort em Rust com diagramas visuais de divisão e conquista, versões recursiva e iterativa, análise Big-O completa." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Merge Sort em Rust Aprenda Merge Sort em Rust com diagramas visuais de divisão e conquista, versões recursiva e iterativa, análise Big-O completa. 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: 1. **Dividir:** divide o vetor ao meio recursivamente. 2. **Conquistar:** quando os subvetores têm tamanho 1, estão ordenados. 3. **Combinar (merge):** intercala dois subvetores ordenados em um único vetor ordenado. ```text 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]`: ```text 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) ```rust /// Merge Sort recursivo (top-down). /// Retorna um novo Vec ordenado, sem modificar o original. fn merge_sort(vetor: &[T]) -> Vec { 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(esquerda: &[T], direita: &[T]) -> Vec { 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) ```rust /// Merge Sort in-place que modifica o slice diretamente. /// Usa um buffer auxiliar para a intercalação. fn merge_sort_in_place(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 = vetor[..meio].to_vec(); let direita: Vec = 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 ```text 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: ```rust fn merge_sort_rastreado(vetor: &[i32], nivel: usize) -> Vec { 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. ```rust /// Merge Sort iterativo (bottom-up). /// Evita a recursão, usando iteração com tamanho de bloco crescente. fn merge_sort_bottom_up(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: ```text 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: ```rust /// Merge Sort otimizado: usa Insertion Sort para partições pequenas. const LIMIAR: usize = 16; fn merge_sort_otimizado(vetor: &[T]) -> Vec { 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(esquerda: &[T], direita: &[T]) -> Vec { 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: ```rust /// Natural Merge Sort — detecta e aproveita sequências já ordenadas. fn natural_merge_sort(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 = vetor[inicio_a..fim_a].to_vec(); let direita: Vec = 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](/algoritmos/heap-sort/) (in-place, O(n log n)) ou [Quick Sort](/algoritmos/quick-sort/). - O vetor for pequeno (n < 50) — o [Insertion Sort](/algoritmos/insertion-sort/) é mais rápido. ## Comparação com Outros Algoritmos | Característica | Merge Sort | [Quick Sort](/algoritmos/quick-sort/) | [Heap Sort](/algoritmos/heap-sort/) | [Insertion Sort](/algoritmos/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 1. **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. 2. **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? 3. **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? 4. **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](/algoritmos/quick-sort/) — alternativa in-place, geralmente mais rápido na prática - [Heap Sort em Rust](/algoritmos/heap-sort/) — in-place com O(n log n) garantido - [Insertion Sort em Rust](/algoritmos/insertion-sort/) — usado como caso base para partições pequenas - [Vec — Vetores Dinâmicos](/stdlib/vec/) — alocação e manipulação de vetores - [Slice — Fatias de Memória](/stdlib/slice/) — divisão de slices com `split_at()` - [Iterator — Iteradores](/stdlib/iterator/) — `chain()`, `zip()` e operações funcionais - [Otimização de Performance em Rust](/artigos/otimizacao-performance/) — técnicas avançadas de performance