TOP 25 ALGORITMOS | Merge Sort

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);
}