As partes ficam pequenas.
O caso-base é um segmento com zero ou um item: ele já está ordenado. Cada chamada divide a região ativa aproximadamente ao meio, até que reste somente esse caso imediato.
03 / sorting
Merge Sort.
Divida em partes pequenas; reconstrua em uma ordem previsível.
/ visualização passo a passo
Mescla duas sequências já ordenadas em uma só.
palco / Mergemotivo / Merge
000 comparações000 escritas0% progresso pronto
telemetria / passo ao vivo
passo atual00input carregado — pronto para executar
etapa de código01destaque sincronizado por linguagem
entrada16elementos em memória
estadoreadycontrole manual
playback observado · ordenação
Duração que aconteceu.
Execuções concluídas nesta bancada, medidas durante o playback ativo no navegador e salvas apenas neste dispositivo.
média / últimas 0—Merge · armazenamento local
sem registros ainda
Execute o algoritmo até o fim para transformar esta bancada em uma série de medições reais.
/ leitura em três sinais
O que a bancada revela?
Mescla duas sequências já ordenadas em uma só. Cada barra representa um item; a cor quente marca a comparação atual e o verde calmo indica que uma posição já não precisa ser revisitada.
quando usarUse quando estabilidade e previsibilidade importam, como em grandes coleções ou dados que chegam em blocos.
complexidade
melhor casoO(n log n)
caso médioO(n log n)
pior casoO(n log n)
Mantém desempenho consistente, ao custo de memória auxiliar; a combinação usa índices para evitar remoções lineares.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara como o número de operações tende a crescer quando n, a quantidade de itens, aumenta.
operações
O(n log n) · Crescimento log-linear
O algoritmo trata todos os itens, mas organiza as decisões em níveis. O termo log representa quantas vezes o problema pode ser dividido ao meio.
Em base 2, 16 itens exigem 4 níveis; 32 itens exigem 5. Dobrar a entrada adiciona apenas um nível.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para observar por que O(n²) acumula trabalho mais depressa que O(n log n) quando a lista cresce. Merge Sort tende a crescer mais devagar do que Bubble Sort quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
Dividir não basta.
A garantia nasce na mesclagem.
A bancada separa a sequência em partes menores, mas é a operação de merge que transforma duas metades já ordenadas em uma única resposta correta. Dois cursores avançam pelas metades e liberam, a cada escolha, o menor item que ainda pode ocupar a próxima posição.
O menor disponível sai primeiro.
Se os dois prefixos estão ordenados, basta comparar os seus primeiros itens. Escolher o menor mantém a saída ordenada; quando uma metade se esgota, o restante da outra pode ser copiado sem nova comparação.
A mesma prova sobe a árvore.
Por hipótese, as duas metades retornam ordenadas. Como a mesclagem preserva todos os itens e produz uma sequência não decrescente, o segmento inteiro também retorna ordenado.
/ custo e estrutura
Todo nível percorre a entrada; a altura cresce em log.
A recorrência T(n) = 2T(n/2) + Θ(n) descreve duas metades e uma mesclagem linear. Como a árvore de divisão tem Θ(log n) níveis, o tempo é Θ(n log n) nos casos melhor, médio e pior — uma garantia que não depende do formato inicial da entrada.
TEMPOΘ(n log n)Também no pior caso.
ESTABILIDADESIMCom preferência pela metade esquerda no empate.
MEMÓRIA EM VETORΘ(n)Buffer auxiliar na versão convencional.
VARIANTE ITERATIVAbottom-upMescla blocos de 1, 2, 4, 8… itens.
DECISÃO DE ENGENHARIA
Troque memória auxiliar por previsibilidade e estabilidade.
Em vetores, o espaço auxiliar linear é a principal contrapartida da versão estável e com custo garantido. Em listas encadeadas, a mesclagem pode reorganizar nós sem o mesmo buffer; para volumes maiores que a memória, blocos ordenados podem ser combinados em uma mesclagem k-way. Implementações práticas ainda alternam os vetores de origem e destino, usam Insertion Sort em blocos pequenos e pulam a mesclagem quando as metades já estão em ordem.
/ por baixo do palcoPseudocódigo e
destaque sincronizado por linguagemPseudocódigo e
implementação.
etapa / 00
input carregado — pronto para executar
O destaque acompanha o mesmo passo que você vê nas barras. Execute em câmera lenta para conectar intenção e efeito.
linha atual comentário de estado
function mergeSort(items) { // Split recursively and merge sorted halves if (items.length <= 1) return items; const middle = Math.floor(items.length / 2); const left = mergeSort(items.slice(0, middle)); const right = mergeSort(items.slice(middle)); return merge(left, right);} function merge(left, right) { const result = []; let leftIndex = 0, rightIndex = 0; while (leftIndex < left.length && rightIndex < right.length) { result.push(left[leftIndex] <= right[rightIndex] ? left[leftIndex++] : right[rightIndex++]); } return result.concat(left.slice(leftIndex), right.slice(rightIndex));}/ mesma entrada · duas leiturasComparação
Comparação
lado a lado.
A / Merge pronto
0comparações0 escritas
B / Bubble pronto
0comparações0 trocas
03 prática
/ decisão de engenhariaOnde esta estratégia
Onde esta estratégia
encaixa?
Use quando estabilidade e previsibilidade importam, como em grandes coleções ou dados que chegam em blocos. A melhor forma de internalizar essa escolha é comparar o mesmo cenário com outras estratégias e observar como as métricas se comportam.
testar no modo corrida