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
- Dividir: divida o array ao meio recursivamente até ter subarrays de tamanho 1
- Conquistar: subarrays de tamanho 1 já estão ordenados
- 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
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 — Alternativa mais rápida na prática, mas O(n²) no pior caso
- Heap Sort em Zig — O(n log n) in-place, mas não estável
- Insertion Sort em Zig — Usado como otimização para partições pequenas
- Array Dinâmico — Estrutura com alocação dinâmica
- Lista Encadeada — Merge Sort é ideal para listas encadeadas