O Merge Sort em JavaScript é um algoritmo clássico de “dividir para conquistar” que simplifica a solução de problemas complexos. Ao contrário do Bubble Sort e do Insertion Sort, que perdem eficiência com grandes volumes de dados, o Merge Sort mantém uma complexidade de tempo O(n log n), garantindo um desempenho consistente. Uma de suas principais vantagens é ser um algoritmo de ordenação estável, ou seja, elementos iguais mantêm suas posições originais, algo útil em bancos de dados e conjuntos de dados ordenados.
Como Funciona o Merge Sort em JavaScript
O Merge Sort utiliza uma abordagem recursiva clara, que pode ser resumida em três passos:
- Dividir: O array é dividido em duas metades, criando subarrays cada vez menores.
- Conquistar: Cada subarray é ordenado recursivamente.
- Combinar: As subarrays ordenadas são unidas para formar um único array ordenado.
Imagine que o array é quebrado em partes até que cada elemento se torne um mini-array individual. A recursão reconstrói o array, comparando os elementos. A beleza do Merge Sort está em sua capacidade de simplificar o problema e construir a solução unindo as partes ordenadas.
Para facilitar a visualização, observe a seguinte representação:
Modificado (acelerado) de Swfung8, licenciado sob CC BY-SA 3.0.
Implementando o Merge Sort em JavaScript
Vamos analisar a implementação do Merge Sort em JavaScript, com comentários detalhados para explicar cada parte do código:
const nums = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4];
function mergeSort(array) {
/*
Condição de saída da recursão: quando há apenas um item na lista, retorna o array.
Este é o nosso caso base - um array de elemento único já está ordenado.
Cada elemento no array eventualmente termina como um array de elemento único: [99], [44], etc.
*/
if (array.length === 1) {
return array;
}
let left = [];
let right = [];
// Math.floor é usado para uma divisão balanceada, tornando left <= right quando o comprimento é ímpar.
// Isso mantém a profundidade da recursão uniforme, evitando desequilíbrio desnecessário.
let mid = Math.floor(array.length / 2);
// Divide o array em porções esquerda e direita:
for (let i = 0; i < mid; i++) {
left.push(array[i]);
}
for (let i = mid; i < array.length; i++) {
right.push(array[i]);
}
// Ordena recursivamente ambas as metades, depois as une
// O || [] garante que sempre passaremos um array mesmo em casos extremos
// Isso evita erros de "Não é possível ler propriedades de indefinido"
return merge(mergeSort(left) || [], mergeSort(right) || []);
}
function merge(left, right) {
// Esta função une dois arrays mantendo os elementos em ordem
const mergedArr = [];
// Usa ponteiros de índice em vez de shift() para manter a eficiência O(n)
// shift() causaria comportamento O(n²) devido à reindexação do array
let i = 0; // índice para array esquerdo
let j = 0; // índice para array direito
// Compara elementos de ambos os arrays e adiciona o menor ao resultado
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
// Adiciona quaisquer elementos restantes do array esquerdo
// Isso é acionado apenas quando o array direito está esgotado, mas o esquerdo ainda tem elementos
while (i < left.length) {
mergedArr.push(left[i]);
i++;
}
// Adiciona quaisquer elementos restantes do array direito
// Isso é acionado apenas quando o array esquerdo está esgotado, mas o direito ainda tem elementos
while (j < right.length) {
mergedArr.push(right[j]);
j++;
}
return mergedArr;
}
const answer = mergeSort(nums);
console.log("answer:", answer);
// Output: [1, 2, 4, 5, 6, 44, 63, 87, 99, 283]
Como podemos ver na implementação acima, o Merge Sort consiste em duas funções principais:
-
A função
mergeSort, que divide recursivamente o array em partes menores até que cada subarray contenha um único elemento. -
A função
merge, que compara elementos de dois subarrays ordenados e os une novamente em um único array ordenado.
Essa separação de responsabilidades torna o algoritmo elegante e eficiente. No início, pode ser complicado entender o que está acontecendo e por que, mas há mais no Merge Sort do que aparenta. Vamos analisar alguns detalhes de implementação que podem ajudar a ter um modelo mental melhor para entender sua mecânica interna.
Detalhes Essenciais da Implementação do Merge Sort
Muitas explicações cobrem a mecânica básica do merge sort, mas alguns aspectos técnicos merecem uma análise mais detalhada para uma compreensão completa.
A Decisão do Math.floor() ao Dividir Arrays
Um detalhe frequentemente negligenciado é a escolha entre Math.floor(), Math.ceil() ou divisão inteira regular ao dividir arrays. Essa decisão impacta significativamente o comportamento do algoritmo.
Usar Math.floor() significa que, quando o comprimento do array é ímpar, o lado esquerdo recebe um elemento a menos que o lado direito. Por exemplo, com um array de comprimento 5:
-
Math.floor(5/2) = 2, então o lado esquerdo recebe os índices [0, 1] e o lado direito recebe [2, 3, 4].
Isso cria uma árvore de recursão balanceada, resultando em um desempenho ideal. Se usássemos Math.ceil(), teríamos uma divisão desbalanceada, o que poderia causar uma recursão mais profunda em um lado e degradar o desempenho.
Casos Limite Comuns
Um erro comum ao estudar o Merge Sort pode ser algo como:
TypeError: Cannot read properties of undefined (reading 'length')
Isso ocorre porque, em certos casos extremos, mergeSort(left) ou mergeSort(right) podem retornar undefined. Uma solução simples é adicionar uma proteção:
return merge(mergeSort(left) || [], mergeSort(right) || []);
O || [] garante que um array sempre chegue à função merge e elimina os erros de verificação de comprimento indefinido.
Evitando a Armadilha do Desempenho O(n²)
Ao trabalhar com grandes quantidades de dados, certos métodos integrados podem introduzir custos de desempenho ocultos. Uma armadilha comum é usar shift() para extrair elementos:
while (left.length && right.length) {
mergedArr.push(left[0] < right[0] ? left.shift() : right.shift());
}
Essa abordagem tem uma falha grave: shift() é executado com complexidade O(n) porque reindexa todo o array após cada operação. Quando realizado repetidamente durante o processo de ordenação, isso cria um comportamento O(n²), reduzindo a eficiência do Merge Sort.
Embora usar métodos como slice() seja conveniente para simplificar a divisão do array, eles têm sua própria complexidade de tempo e espaço. Estar atento a como as funções integradas operam pode ajudar a evitar sobrecarga desnecessária.
Uma abordagem mais eficiente para unir usa ponteiros de índice (i e j) para manter a complexidade O(n):
let i = 0
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
Análise da Complexidade de Tempo e Espaço
As características de desempenho do Merge Sort são as seguintes:
-
Complexidade de Tempo:
- Melhor Caso: O(n log n)
- Caso Médio: O(n log n)
- Pior Caso: O(n log n)
Esse desempenho consistente em todos os cenários torna o Merge Sort altamente confiável, ao contrário de algoritmos de ordenação instáveis, que podem ter desempenho inferior em alguns casos.
- Complexidade de Espaço: O(n)
O Merge Sort requer memória adicional proporcional ao tamanho da entrada. Isso se deve à criação de novos arrays durante o processo de união.
Vantagens e Desvantagens do Merge Sort
Vantagens:
- Desempenho O(n log n) previsível, independentemente dos dados de entrada
- Ordenação estável (mantém a ordem relativa de elementos iguais)
- Adequado para listas encadeadas e ordenação externa
Desvantagens:
- Requisito de espaço extra O(n)
- Ligeiramente mais lento que o Quicksort para ordenação de arrays na memória
- Desnecessário para arrays pequenos (onde algoritmos mais simples podem ter um desempenho melhor)
Quando Usar o Merge Sort
- Quando você precisa de ordenação estável
- Ao lidar com listas encadeadas (o Merge Sort é particularmente eficiente para listas encadeadas)
- Quando o desempenho do pior caso é importante (ao contrário do Quicksort, que pode degradar para O(n²))
- Para ordenação externa, onde os dados não cabem na memória
Aplicações Práticas e Casos de Uso
- Sistemas de banco de dados: Ao ordenar grandes conjuntos de dados que não cabem na memória
- Ordenação externa: Usado em sistemas que precisam ordenar dados armazenados em disco
- Requisitos de ordenação estável: Quando a ordem dos elementos iguais é importante
- Computação paralela: O Merge Sort é facilmente paralelizável
O Merge Sort é um dos exemplos mais conhecidos da abordagem “dividir para conquistar”, que impulsiona muitos algoritmos eficientes. Mesmo que exija mais memória do que alguns algoritmos de ordenação, seu desempenho consistente e estabilidade o tornam uma escolha sólida para diversas aplicações.
O Merge Sort pode não ser a escolha ideal para todas as necessidades de ordenação (especialmente com arrays pequenos ou quando a memória é limitada), mas entendê-lo aprofunda seu pensamento algorítmico e prepara você para lidar com problemas computacionais mais complexos. Se você está buscando mais informações sobre o mundo da tecnologia, não deixe de conferir este artigo sobre o novo driver Adrenalin 25.3.1 da AMD que adiciona suporte para a série RX 9070.
Além disso, se você é um entusiasta de jogos, pode se interessar por este artigo sobre os novos jogos adicionados ao GeForce NOW, como Monster Hunter Wilds e FragPunk. E para os fãs de filmes, não percam esta análise completa dos filmes dos Irmãos Russo.
Para quem busca novas formas de organização, o Microsoft explicita as vantagens do backup de arquivos do M365 no OneDrive, facilitando o dia a dia. E se você está de olho nas novidades da Apple, confira este artigo sobre a nova geração do Mac Studio com chips M4 Max e M3 Ultra.
Este conteúdo foi auxiliado por Inteligência Artificial, mas escrito e revisado por um humano.
Via Dev.to