¿Qué es Merge Sort?

Merge Sort es un algoritmo de ordenamiento eficiente que utiliza el enfoque de "divide y vencerás". Divide el arreglo en mitades hasta que cada subarreglo tiene un solo elemento, y luego los combina en orden ascendente.

El Código

                
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Ejemplo de uso
const array = [38, 27, 43, 3, 9, 82, 10];
console.log("Array ordenado:", mergeSort(array));
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo desordenado (arr).
• Salida: El arreglo ordenado de menor a mayor.
• Método:
  • Divide el arreglo en dos mitades recursivamente hasta que cada subarreglo tiene un solo elemento.
  • Combina (merge) los subarreglos en un nuevo arreglo en orden ascendente.
• Complejidad:
  • Peor caso: O(n log n).
  • Mejor caso: O(n log n).
  • Promedio: O(n log n).
• Ventajas: Es consistente en su rendimiento, y funciona bien para arreglos grandes.
• Desventajas: Requiere espacio adicional proporcional al tamaño del arreglo para realizar las combinaciones.

Ejemplo de Ejecución

Arreglo inicial: [38, 27, 43, 3, 9, 82, 10]

Proceso de división:

• Divide en [38, 27, 43] y [3, 9, 82, 10].
• Divide [38, 27, 43] en [38] y [27, 43].
• Divide [27, 43] en [27] y [43].
• Divide [3, 9, 82, 10] en [3, 9] y [82, 10].
• Divide [3, 9] en [3] y [9].
• Divide [82, 10] en [82] y [10].

Proceso de combinación:

• Combina [27] y [43] en [27, 43].
• Combina [38] y [27, 43] en [27, 38, 43].
• Combina [3] y [9] en [3, 9].
• Combina [82] y [10] en [10, 82].
• Combina [3, 9] y [10, 82] en [3, 9, 10, 82].
• Combina [27, 38, 43] y [3, 9, 10, 82] en [3, 9, 10, 27, 38, 43, 82].

Arreglo final ordenado: [3, 9, 10, 27, 38, 43, 82]

Información Adicional

Merge Sort es un algoritmo ampliamente utilizado debido a su consistencia y estabilidad. Aunque requiere espacio adicional, su complejidad O(n log n) lo hace eficiente para grandes volúmenes de datos, tanto en memoria como en discos.