Algoritmos de Ordenamiento

Los algoritmos de ordenamiento ilustran perfectamente cómo la complejidad afecta el rendimiento real. Bubble Sort y Insertion Sort son O(n²): simples de entender pero inutilizables para datos grandes. Merge Sort divide recursivamente el array a la mitad, ordena cada mitad y las fusiona: siempre O(n log n) pero usa O(n) de memoria extra.

Quick Sort elige un pivote y divide el array en "menores" y "mayores": O(n log n) promedio, O(n²) en el peor caso, pero O(log n) de espacio.

Comprender Merge Sort es fundamental porque el patrón "divide y conquista" que usa aparece en decenas de otros algoritmos. La idea: dividir el problema en dos mitades más pequeñas, resolver cada mitad recursivamente, y combinar los resultados.

También te enseña el árbol de recursión para calcular complejidad: si cada nivel hace O(n) trabajo y hay O(log n) niveles, la complejidad total es O(n log n). Los lenguajes modernos usan TimSort (híbrido de Merge Sort e Insertion Sort) en sus métodos sort() nativos.

// Merge Sort - O(n log n) tiempo, O(n) espacio
// Divide y vencerás
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const izq = mergeSort(arr.slice(0, mid));
  const der = mergeSort(arr.slice(mid));
  
  return merge(izq, der);
}

function merge(izq, der) {
  const result = [];
  let i = 0, j = 0;
  
  while (i < izq.length && j < der.length) {
    if (izq[i] <= der[j]) result.push(izq[i++]);
    else result.push(der[j++]);
  }
  
  return [...result, ...izq.slice(i), ...der.slice(j)];
}

// Quick Sort - O(n log n) promedio, O(n²) peor caso
function quickSort(arr, bajo = 0, alto = arr.length - 1) {
  if (bajo >= alto) return;
  
  const pivoteIdx = particion(arr, bajo, alto);
  quickSort(arr, bajo, pivoteIdx - 1);
  quickSort(arr, pivoteIdx + 1, alto);
}

function particion(arr, bajo, alto) {
  const pivote = arr[alto];
  let i = bajo - 1;
  
  for (let j = bajo; j < alto; j++) {
    if (arr[j] <= pivote) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i+1], arr[alto]] = [arr[alto], arr[i+1]];
  return i + 1;
}

// Comparación de algoritmos de ordenamiento:
// Bubble Sort: O(n²) - solo para aprender
// Selection Sort: O(n²) - solo para aprender
// Insertion Sort: O(n²) pero O(n) para casi ordenados
// Merge Sort: O(n log n) siempre - estable
// Quick Sort: O(n log n) promedio - in-place
// Tim Sort: O(n log n) - el que usa Python y Java