TOP 25 ALGORITMOS | Merge Sort

É um algoritmo de que funciona dividindo recursivamente o array de entrada em subarrays menores e classificando esses subarrays e, em seguida, mesclando-os novamente para obter o array classificado.

📁 | Resumo

🤖 | Código

function merge(arr, left, mid, right) {
  const n1 = mid - left + 1;
  const n2 = right - mid;


  // Cria matrizes temporárias
  const L = new Array(n1);
  const R = new Array(n2);


  // Copia dados para matrizes temporárias L[] e R[]
  for (let i = 0; i < n1; i++)
      L[i] = arr[left + i];
  for (let j = 0; j < n2; j++)
      R[j] = arr[mid + 1 + j];


  let i = 0, j = 0;
  let k = left;


  // Mescla as matrizes temporárias de volta em arr[left..right]
  while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
          arr[k] = L[i];
          i++;
      } else {
          arr[k] = R[j];
          j++;
      }
      k++;
  }


  // Copie os elementos restantes de L[], se houver algum
  while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
  }


  // Copie os elementos restantes de R[], se houver algum
  while (j < n2) {
      arr[k] = R[j];
      j++;
      k++;
  }
}


function mergeSort(arr, left, right) {
  if (left >= right)
      return;


  const mid = Math.floor(left + (right - left) / 2);
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  merge(arr, left, mid, right);
}

🕰️ | Complexidade de Tempo

O tempo de execução do algoritmo cresce em função do tamanho da entrada n multiplicado pelo logaritmo de n. Esse tipo de complexidade geralmente aparece em algoritmos que combinam operações lineares com alguma forma de divisão e conquista. Logo, sua complexidade de tempo será descrita por O(n ∙ log(n)).

✦ Melhor Cenário: se a lista já estiver classificada, ou seja, ordenada, O(n ∙ log (n));

✦ Cenário Comum: se a lista estiver classificada de forma aleatória, O(n ∙ log (n));

✦ Pior Cenário: se a lista estiver classificada de forma reversa (decrescente), O(n ∙ log (n));

📦 | Complexidade de Espaço

Requer apenas um espaço de memória extra temporária. Logo, sua complexidade de espaço será descrita por O(n).

✔️ | Vantagens

✦ Estável e eficiente;

✦ Simples de Implementar;

✦ Processamento em paralelo;

❌ | Desvantagens

✦ Requer memória adicional;

✦ Mais lento que o Quick Sort;