Merge Sort

Conceito

Merge sort é o exemplo canônico de divide-and-conquer: divide ao meio, ordena cada metade recursivamente, e intercala as duas metades ordenadas.

Por que é O(n log n) — e essa é a conta que vale entender de verdade:

• dividir pela metade repetidamente dá log₂ n níveis de profundidade
• em cada nível, a intercalação percorre todos os n elementos: O(n) de trabalho
• total: n × log n

Formalmente é T(n) = 2·T(n/2) + O(n), o caso mais reconhecível do teorema mestre. A estrutura da recorrência é o algoritmo: dois subproblemas de metade do tamanho, mais trabalho linear para juntar.

Por que é estável e o quick sort não: na intercalação, quando os dois elementos da frente são iguais, você escolhe o da esquerda. Uma linha de código — a diferença entre <= e < — decide a estabilidade.

Estabilidade importa quando você ordena por múltiplas chaves em sequência: ordene por nome, depois por departamento, e com um sort estável os nomes continuam ordenados dentro de cada departamento. Com instável, a primeira ordenação é perdida.

O custo de memória: O(n) para o buffer de intercalação. É isso que:

• o desqualifica em memória restrita, e comparado ao quick sort in-place
• o qualifica para dados que não cabem na memória

Esse segundo ponto é o mais interessante. Em external sort, você ordena pedaços que caibam na RAM, grava cada um, e intercala os arquivos lendo sequencialmente de cada um. A intercalação precisa apenas de um elemento de cada fluxo por vez — e leitura sequencial é exatamente o que disco e rede fazem bem. Merge sort é o algoritmo de ordenação de dados grandes por causa do padrão de I/O, não da complexidade.

Em Go

slices.Sort não é merge sort — é pdqsort (ver 3. Quick Sort), e é instável.

Para estabilidade você pede explicitamente:

sort.Stable e slices.SortStableFunc usam symmerge, uma intercalação in-place — ela troca memória O(n) por trabalho extra, ficando O(n log² n) no pior caso. Ou seja: Go escolheu não gastar memória, e paga em tempo.

Na prática, SortStable é cerca de duas vezes mais lento que Sort. Estabilidade não é grátis, e a API te obriga a escolher — o que é bom: em Java Arrays.sort de objetos é estável e de primitivos não, sem você notar.

Quando você realmente precisa de estável em Go: ordenação por múltiplas chaves em passadas separadas. Se você pode expressar todas as chaves num único comparador (cmp.Or desde Go 1.22 encadeia comparações), use SortFunc instável — é mais rápido e mais claro.

Respostas às perguntas-guia

1. Por que dividir ao meio dá log n níveis, e cada nível custa n?

Conceito: dividir por 2 até chegar a 1 leva log₂ n passos. Em cada nível, a soma dos tamanhos dos subproblemas é n, e a intercalação é linear no tamanho — então cada nível custa O(n) no total.

Em Go: nada específico; é a recorrência, não a linguagem.

2. Por que ele é estável e o quick sort não?

Conceito: porque na intercalação o empate é resolvido a favor da esquerda. O quick sort troca elementos distantes durante o particionamento, destruindo a ordem relativa.

Em Go: é a razão de existirem Sort e SortStable como funções separadas — a implementação por baixo é outra.

3. Qual o custo de memória, e por que isso o desqualifica em certos contextos?

Conceito: O(n) de buffer. Em memória restrita ou em hot path com alocação, isso é proibitivo.

Em Go, isso é agravado porque o buffer é uma alocação no heap por chamada, e alocação é pressão de GC (2. Stack vs Heap). É parte do motivo de a stdlib ter escolhido pdqsort in-place como padrão e symmerge (in-place) para o estável.

4. Por que ele é a escolha natural para ordenar dados que não cabem na memória?

Conceito: porque a intercalação só precisa de um elemento de cada fluxo por vez, e lê cada fluxo sequencialmente. Sequencial é o padrão de acesso que disco e rede otimizam.

Em Go: é o padrão que você implementaria com bufio.Scanner por arquivo e um container/heap de k fluxos — o k-way merge. E é literalmente como um LSM-tree (RocksDB, Cassandra) compacta seus níveis.

Trade-offs

Do conceito:

• O(n log n) garantido em todos os casos — merge sort não tem pior caso ruim, ao contrário do quick sort.
• Estável, e paga O(n) de memória por isso.
• Padrão de acesso sequencial: pior para cache que o particionamento do quick sort na memória, e melhor que tudo em disco.

Em Go:

• A stdlib te dá estabilidade sem custo de memória (symmerge), pagando em tempo (~2×). É uma troca diferente da usual, e vale saber que ela foi feita.
• sort.Slice usa reflexão e é mais lento que slices.SortFunc; em código novo, não há razão para usar o pacote sort para ordenar slices.
• Encadear comparadores com cmp.Or (Go 1.22+) frequentemente elimina a necessidade de ordenação estável.

Exemplo prático

package main

import (
	"cmp"
	"fmt"
	"math/rand"
	"slices"
)

// Merge sort explícito: a intercalação é o algoritmo.
func mergeSort(s []int) []int {
	if len(s) <= 1 {
		return s
	}
	meio := len(s) / 2
	esq := mergeSort(slices.Clone(s[:meio]))
	dir := mergeSort(slices.Clone(s[meio:]))
	return intercala(esq, dir)
}

func intercala(a, b []int) []int {
	out := make([]int, 0, len(a)+len(b)) // O(n) de memória: o preço
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] <= b[j] { // <= e não <: É AQUI que nasce a estabilidade
			out = append(out, a[i])
			i++
		} else {
			out = append(out, b[j])
			j++
		}
	}
	return append(append(out, a[i:]...), b[j:]...)
}

type Func struct {
	Nome, Depto string
}

// A verificação: dentro de cada departamento, os nomes continuam em ordem?
func nomesOrdenadosPorDepto(fs []Func) bool {
	for i := 1; i < len(fs); i++ {
		if fs[i].Depto == fs[i-1].Depto && fs[i].Nome < fs[i-1].Nome {
			return false
		}
	}
	return true
}

func porNome(a, b Func) int  { return cmp.Compare(a.Nome, b.Nome) }
func porDepto(a, b Func) int { return cmp.Compare(a.Depto, b.Depto) }

func main() {
	fmt.Println(mergeSort([]int{5, 2, 9, 1, 5, 6}))

	// 60 registros: preciso passar do limiar de 12, abaixo do qual o pdqsort
	// usa insertion sort e acaba estável POR ACIDENTE.
	deptos := []string{"ti", "vendas", "rh"}
	pessoas := make([]Func, 0, 60)
	for i := 0; i < 60; i++ {
		pessoas = append(pessoas, Func{fmt.Sprintf("n%02d", i), deptos[i%3]})
	}
	r := rand.New(rand.NewSource(42)) // semente fixa: resultado reproduzível
	r.Shuffle(len(pessoas), func(i, j int) { pessoas[i], pessoas[j] = pessoas[j], pessoas[i] })

	// 2 passadas com sort INSTÁVEL: a primeira ordenação é perdida, sem erro nenhum
	instavel := slices.Clone(pessoas)
	slices.SortFunc(instavel, porNome)
	slices.SortFunc(instavel, porDepto)

	// 2 passadas com sort ESTÁVEL: a primeira ordenação sobrevive
	estavel := slices.Clone(pessoas)
	slices.SortStableFunc(estavel, porNome)
	slices.SortStableFunc(estavel, porDepto)

	// 1 passada com comparador encadeado: não depende de estabilidade nenhuma
	uma := slices.Clone(pessoas)
	slices.SortFunc(uma, func(a, b Func) int { return cmp.Or(porDepto(a, b), porNome(a, b)) })

	fmt.Println("nomes ainda ordenados dentro de cada depto?")
	fmt.Println("  instável, 2 passadas:", nomesOrdenadosPorDepto(instavel))
	fmt.Println("  estável,  2 passadas:", nomesOrdenadosPorDepto(estavel))
	fmt.Println("  cmp.Or,   1 passada: ", nomesOrdenadosPorDepto(uma))

	// as três estão ordenadas por departamento — a diferença é invisível daqui
	fmt.Println("todas ordenadas por depto?",
		slices.IsSortedFunc(instavel, porDepto) &&
			slices.IsSortedFunc(estavel, porDepto) &&
			slices.IsSortedFunc(uma, porDepto))

	// k-way merge: o padrão do external sort
	fluxos := [][]int{{1, 4, 9}, {2, 5, 8}, {3, 6, 7}}
	fmt.Println("k-way merge:", kWayMerge(fluxos))
}

// Intercala k fluxos ordenados lendo UM elemento de cada por vez.
func kWayMerge(fluxos [][]int) []int {
	pos := make([]int, len(fluxos))
	total := 0
	for _, f := range fluxos {
		total += len(f)
	}
	out := make([]int, 0, total)
	for len(out) < total {
		melhorF, melhorV := -1, 0
		for i, f := range fluxos {
			if pos[i] < len(f) && (melhorF == -1 || f[pos[i]] < melhorV) {
				melhorF, melhorV = i, f[pos[i]]
			}
		}
		out = append(out, melhorV)
		pos[melhorF]++
	}
	return out
}

Relacionado

• 3. Quick Sort — a troca oposta: in-place, pior caso ruim
• 5. Recursão — semana 3, divide-and-conquer é recursão com medida clara
• 1. Notação Big-O — semana 2, de onde vem o n log n
• 6. Transações e ACID — semana 9, LSM-trees compactam por k-way merge

---

Parte de Semana 04 - Algoritmos Essenciais · 00 - MOC Fundamentos de Programação