Ordenação por Intercalação: Dividir, Ordenar, Intercalar
Implemente a ordenação por intercalação recursivamente, acompanhe a árvore de divisão e conquista e explique por que ela garante O(n log n) em todos os casos.
Ordenação por Intercalação: Dividir, Ordenar, Intercalar é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Intuição de Dividir e Conquistar
A ordenação por intercalação é um algoritmo clássico de dividir e conquistar: divida o vetor ao meio, ordene recursivamente cada metade e depois faça merge das duas metades ordenadas em um único resultado ordenado. A ideia é que fazer merge de dois vetores ordenados requer O(n) — muito menos que ordená-los do zero. Essa decomposição produz uma árvore de recursão com log n níveis, cada um exigindo O(n) de trabalho de intercalação, resultando no limite ideal de O(n log n) para ordenações por comparação.
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]A Etapa de Intercalação Explicada
Para mesclar dois vetores ordenados, mantenha dois ponteiros, um para cada metade. Compare os primeiros elementos; copie o menor para a saída e avance o ponteiro correspondente. Quando uma metade se esgotar, copie diretamente o restante da outra metade. Isso requer tempo O(n) e espaço O(n) para o vetor de saída. A etapa de merge é o núcleo algorítmico da ordenação por intercalação — compreenda-a profundamente.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Implementação completa da ordenação por intercalação
Combinando divisão e intercalação: as chamadas recursivas reduzem o problema pela metade até restarem elementos únicos (trivialmente ordenados); em seguida, as chamadas de intercalação os recombinam. Cada nível da árvore de recursão intercala o mesmo total de n elementos (distribuídos entre várias intercalações). A profundidade da recursão é log₂(n), resultando em tempo total O(n log n) e espaço auxiliar O(n) para os vetores de saída da intercalação, além da profundidade O(log n) da pilha de chamadas.
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Árvore de recursão da ordenação por intercalação
Visualize a árvore de recursão da ordenação por intercalação para n=8: o nível 0 tem um vetor com 8 elementos; o nível 1 tem dois vetores com 4 elementos; o nível 2 tem quatro vetores com 2 elementos; o nível 3 tem oito elementos únicos (casos-base). Ao subir novamente, o nível 3→2 intercala um total de 8 elementos, o nível 2→1 intercala um total de 8, e o nível 1→0 intercala um total de 8. Isso corresponde a 3 níveis × 8 elementos = 24 operações ≈ 8 × log₂(8) = 24. Isso confirma O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Ordenação por intercalação no próprio vetor
A ordenação por intercalação recursiva padrão aloca espaço auxiliar O(n) para a saída da intercalação. Existe uma ordenação por intercalação no próprio vetor, mas ela é complexa e tem constantes altas — raramente é solicitada em entrevistas. A pergunta complementar mais comum em entrevistas é: “É possível fazer a ordenação por intercalação usando O(1) de espaço adicional?”. A resposta correta é: “Em teoria, sim, mas as implementações práticas sacrificam o espaço O(n) ou acrescentam complexidade; o Timsort do Python usa espaço O(n) para a intercalação.”
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]A ordenação por intercalação é estável
A ordenação por intercalação é estável: elementos iguais da metade esquerda sempre aparecem antes dos elementos iguais da metade direita na saída intercalada. Isso é garantido usando <= (e não <) ao escolher o elemento da esquerda. A estabilidade é importante para ordenações por várias chaves. sorted() e list.sort() integrados ao Python usam Timsort, que também é estável e O(n log n), o que os torna a escolha segura para todo código de produção.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Intercalar k vetores ordenados
É possível intercalar k vetores ordenados com um total de n elementos intercalando repetidamente pares (como em um chaveamento de torneio), em tempo O(n log k). Cada nível de intercalação processa n elementos, e há log k níveis. Como alternativa, use um montículo mínimo de tamanho k: insira o menor elemento restante de cada vetor, remova o mínimo e insira o próximo elemento desse vetor. A abordagem do montículo também é O(n log k), mas usa a memória com mais eficiência quando k é muito grande.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Contar inversões com a ordenação por intercalação
A contagem de inversões (pares em que a[i] > a[j] e i < j) em O(n log n) usa uma ordenação por intercalação modificada. Durante a etapa de intercalação, quando um elemento do subvetor direito é menor que um elemento do subvetor esquerdo, ele forma uma inversão com todos os elementos restantes do subvetor esquerdo. Nesse momento, adicione len(left) - i à contagem.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Ordenação por intercalação versus ordenação rápida
A ordenação por intercalação garante O(n log n) em todos os casos, é estável e é a melhor escolha para listas encadeadas e ordenação externa. A ordenação rápida tem caso médio O(n log n), mas pior caso O(n²), funciona no próprio vetor (espaço de pilha O(log n)) e costuma ser mais rápida na prática devido à eficiência de cache em vetores. A ordenação integrada ao Python usa Timsort (uma variante da ordenação por intercalação) — é sempre a escolha padrão correta.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Ordenação externa: ordenação por intercalação em grande escala
A ordenação por intercalação é o algoritmo por trás da ordenação externa (ordenação de dados grandes demais para caber na RAM). Os dados são lidos em blocos, cada bloco é ordenado na memória e os blocos são intercalados a partir do disco. A etapa de intercalação lê um elemento por vez de cada sequência ordenada, mantendo apenas O(k) elementos na memória de cada vez (um por sequência). É por isso que a ordenação por intercalação é usada em bancos de dados, no Hadoop MapReduce e nos algoritmos clássicos de ordenação em fita.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Resumo da ordenação por intercalação e dicas para entrevistas
Em entrevistas, implementar a ordenação por intercalação de forma clara demonstra domínio da recursão, da etapa de intercalação e da estratégia dividir para conquistar. Perguntas complementares comuns:
- Por que O(n log n) e não O(n²)? (log n níveis × n de trabalho por nível)
- Ela é estável? (Sim, use <= na intercalação)
- Quanto espaço ela usa? (O(n) auxiliar + pilha O(log n))
- É possível fazê-la de forma iterativa? (Sim, usando a ordenação por intercalação de baixo para cima)
- Como você a usaria em uma lista encadeada? (É mais fácil do que em um vetor — não há custo O(n) de fatias; use dois ponteiros, um lento e um rápido, para encontrar o ponto médio)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: a ordenação por intercalação divide o vetor no ponto médio, ordena recursivamente cada metade e intercala as duas metades ordenadas em O(n), produzindo um tempo total O(n log n) ao longo de log n níveis de recursão; a etapa de intercalação usa <= para escolher o elemento da esquerda em caso de empate, garantindo a estabilidade; e a ordenação por intercalação é o algoritmo escolhido para listas encadeadas, ordenação externa e situações em que a estabilidade é necessária — enquanto a ordenação rápida é preferível para vetores mantidos na memória quando o espaço é limitado. Em seguida, implementaremos a ordenação rápida e exploraremos estratégias de seleção do pivô.
Perguntas Frequentes
A aula “Ordenação por Intercalação: Dividir, Ordenar, Intercalar” é grátis?
Sim — o texto completo de “Ordenação por Intercalação: Dividir, Ordenar, Intercalar” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Ordenação por Intercalação: Dividir, Ordenar, Intercalar”?
Implemente a ordenação por intercalação recursivamente, acompanhe a árvore de divisão e conquista e explique por que ela garante O(n log n) em todos os casos. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Ordenação por Intercalação: Dividir, Ordenar, Intercalar”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Ordenação por Bolhas e por Inserção
- Ordenação por Intercalação: Dividir, Ordenar, Intercalar
- Quick Sort e Seleção do Pivô
- Ordenações sem Comparação e o sort() do Python