Merge Sort em JavaScript

Explorando Algoritmos com Javascript: Merge Sort

by

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:

  1. Dividir: O array é dividido em duas metades, criando subarrays cada vez menores.
  2. Conquistar: Cada subarray é ordenado recursivamente.
  3. 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:

javascript-merge-sort-visualization

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:

  1. A função mergeSort, que divide recursivamente o array em partes menores até que cada subarray contenha um único elemento.
  2. 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

  1. Sistemas de banco de dados: Ao ordenar grandes conjuntos de dados que não cabem na memória
  2. Ordenação externa: Usado em sistemas que precisam ordenar dados armazenados em disco
  3. Requisitos de ordenação estável: Quando a ordem dos elementos iguais é importante
  4. 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

Leave a Comment