--- title: "Merge Sort em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/merge-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/merge-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo Merge Sort implementado em Zig. Explicação completa com código funcional, análise de complexidade O(n log n) e exemplos." date: "2026-02-21" author: "Zig Brasil" --- # Merge Sort em Zig — Implementação e Explicação Aprenda o algoritmo Merge Sort implementado em Zig. Explicação completa com código funcional, análise de complexidade O(n log n) e exemplos. # Merge Sort em Zig — Implementação e Explicação O **Merge Sort** (ordenação por intercalação) é um algoritmo de ordenação baseado na técnica de **divisão e conquista**. Ele divide recursivamente o array ao meio, ordena cada metade e depois intercala (merge) as duas metades ordenadas. É um dos algoritmos de ordenação mais eficientes, com complexidade garantida O(n log n). ## Como Funciona 1. **Dividir**: divida o array ao meio recursivamente até ter subarrays de tamanho 1 2. **Conquistar**: subarrays de tamanho 1 já estão ordenados 3. **Combinar**: intercale (merge) os subarrays ordenados para formar arrays maiores ordenados ### Visualização do Processo ``` 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] [3] [9] [82] [10] Intercalação (merge): [38] [27] [3] [9] [82] [10] \ / \ / \ / [27, 38] [43] [3, 9] [10, 82] \ / \ / [27, 38, 43] [3, 9, 10, 82] \ / [3, 9, 10, 27, 38, 43, 82] ✓ ``` ## Implementação em Zig ```zig const std = @import("std"); const Allocator = std.mem.Allocator; /// Merge Sort genérico usando allocator para memória auxiliar. pub fn mergeSort(comptime T: type, allocator: Allocator, items: []T) !void { if (items.len <= 1) return; // Aloca buffer auxiliar uma única vez const aux = try allocator.alloc(T, items.len); defer allocator.free(aux); mergeSortRecursivo(T, items, aux); } fn mergeSortRecursivo(comptime T: type, items: []T, aux: []T) void { if (items.len <= 1) return; const meio = items.len / 2; // Ordena as duas metades recursivamente mergeSortRecursivo(T, items[0..meio], aux[0..meio]); mergeSortRecursivo(T, items[meio..], aux[meio..]); // Intercala as duas metades ordenadas merge(T, items, meio, aux); } fn merge(comptime T: type, items: []T, meio: usize, aux: []T) void { // Copia para o buffer auxiliar @memcpy(aux[0..items.len], items); var i: usize = 0; // índice na metade esquerda var j: usize = meio; // índice na metade direita var k: usize = 0; // índice no resultado while (i < meio and j < items.len) { if (aux[i] <= aux[j]) { items[k] = aux[i]; i += 1; } else { items[k] = aux[j]; j += 1; } k += 1; } // Copia elementos restantes da metade esquerda while (i < meio) { items[k] = aux[i]; i += 1; k += 1; } // Elementos restantes da direita já estão no lugar while (j < items.len) { items[k] = aux[j]; j += 1; k += 1; } } /// Merge Sort bottom-up (iterativo), sem recursão. pub fn mergeSortBottomUp(comptime T: type, allocator: Allocator, items: []T) !void { if (items.len <= 1) return; const aux = try allocator.alloc(T, items.len); defer allocator.free(aux); var largura: usize = 1; while (largura < items.len) : (largura *= 2) { var inicio: usize = 0; while (inicio < items.len) { const meio = @min(inicio + largura, items.len); const fim = @min(inicio + 2 * largura, items.len); if (meio < fim) { const slice = items[inicio..fim]; const aux_slice = aux[inicio..fim]; merge(T, slice, meio - inicio, aux_slice); } inicio += 2 * largura; } } } pub fn main() !void { const stdout = std.io.getStdOut().writer(); var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); const allocator = gpa.allocator(); var numeros = [_]i32{ 38, 27, 43, 3, 9, 82, 10 }; try stdout.print("Original: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); try mergeSort(i32, allocator, &numeros); try stdout.print("Ordenado: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); // Versão bottom-up var nums2 = [_]i32{ 5, 1, 4, 2, 8, 3, 7, 6 }; try mergeSortBottomUp(i32, allocator, &nums2); try stdout.print("Bottom-up: ", .{}); for (nums2) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Melhor caso** | O(n log n) | O(n) | | **Caso médio** | O(n log n) | O(n) | | **Pior caso** | O(n log n) | O(n) | ### Por que O(n log n)? A cada nível de recursão, o trabalho total de intercalação é O(n). Como dividimos o array ao meio repetidamente, há `log₂(n)` níveis. Portanto: `O(n) × O(log n) = O(n log n)`. ### Nota sobre Memória O Merge Sort requer O(n) de memória auxiliar para o buffer de intercalação. Em Zig, isso é explicitado pelo uso do `Allocator`, tornando o custo de memória transparente. ## Características - **Estável**: Sim — preserva a ordem de elementos iguais - **In-place**: Não — requer O(n) de memória adicional - **Adaptativo**: Não — sempre faz O(n log n) operações - **Paralelizável**: Sim — as duas metades podem ser ordenadas em paralelo - **Desempenho garantido**: O(n log n) em todos os casos ## Quando Usar - **Estabilidade é necessária**: quando a ordem de elementos iguais importa - **Desempenho previsível**: quando O(n log n) no pior caso é essencial - **Dados em disco**: excelente para ordenação externa (external sort) - **Listas encadeadas**: muito eficiente, pois merge não precisa de memória extra ## Recursos Relacionados - [Quick Sort em Zig](/algoritmos/quick-sort/) — Alternativa mais rápida na prática, mas O(n²) no pior caso - [Heap Sort em Zig](/algoritmos/heap-sort/) — O(n log n) in-place, mas não estável - [Insertion Sort em Zig](/algoritmos/insertion-sort/) — Usado como otimização para partições pequenas - [Array Dinâmico](/estruturas-dados/array-dinamico/) — Estrutura com alocação dinâmica - [Lista Encadeada](/estruturas-dados/lista-encadeada/) — Merge Sort é ideal para listas encadeadas