1 - Introducción a los algoritmos de ordenamiento eficientes

En esta primera lección introducimos el enfoque de ordenamientos eficientes: algoritmos que escalan mejor que las alternativas cuadráticas. Todos los ejemplos pueden compilarse en C y sirven como base para las implementaciones que veremos a lo largo del tutorial.

1.1 ¿Por qué los ordenamientos clásicos no escalan?

Algoritmos como Bubble Sort, Insertion Sort o Selection Sort repiten comparaciones de forma doblemente anidada. El costo O(n^2) crece rápido:

• Para n = 10 000 elementos, un método cuadrático realiza en el orden de 100 millones de comparaciones.
• El tiempo se duplica cada vez que duplicamos el tamaño de entrada, algo inviable para flujos en tiempo real.
• La localización en memoria suele ser peor: muchas pasadas implican más fallos de caché y menor throughput.

Por eso necesitamos algoritmos que reduzcan el número de comparaciones y mejoren el acceso a memoria.

1.2 Noción de tiempo O(n log n)

La mayoría de los ordenamientos eficientes basados en comparación alcanzan O(n log n). Esto significa que al duplicar n el trabajo crece un poco más que linealmente, pero muy por debajo de n^2. Por ejemplo:

• Con n = 10 000, n log n ronda 132 000, frente a 100 millones de un algoritmo cuadrático.
• Esta complejidad proviene del patrón de dividir la entrada, ordenar subproblemas y combinarlos.
• En la práctica, también importa la constante oculta: pivotear bien en Quick Sort u optimizar la mezcla en Merge Sort marca diferencias.

1.3 ¿Qué es división y conquista?

Es una estrategia en la que partimos el problema en porciones más pequeñas, resolvemos cada una y luego combinamos los resultados. Merge Sort y Quick Sort son ejemplos clásicos. Un esqueleto típico en C luce así:

void mergesort(int *valores, int inicio, int fin) {
  if (inicio >= fin) {
    return;
  }
  int medio = (inicio + fin) / 2;
  mergesort(valores, inicio, medio);
  mergesort(valores, medio + 1, fin);
  merge(valores, inicio, medio, fin); // combina dos mitades ordenadas
}

La recursión genera el factor log n (altura del árbol de llamadas), y el trabajo lineal al mezclar produce el factor n.

1.4 Ordenamientos internos (en memoria) vs externos (en disco)

No todos los datos caben en memoria. Distinguimos:

• Internos: operan completamente en RAM. Buscan minimizar comparaciones y movimientos (Quick Sort, Heap Sort).
• Externos: procesan datos que residen en disco o llegan en flujos. Priorizan lecturas secuenciales y buffers (External Merge Sort).
• El diseño del algoritmo depende del modelo de costo: tiempos de E/S, tamaño de página, ancho de banda y políticas de caché.

1.5 Importancia en aplicaciones reales

Elegir bien el ordenamiento impacta directamente en productos y servicios:

• Bases de datos: los sort-merge joins y la generación de índices requieren ordenamientos externos estables.
• Motores de búsqueda: los resultados se fusionan y priorizan usando pipelines de ordenamiento masivo.
• Videojuegos: listas de render y sistemas de eventos dependen de ordenar por prioridad o distancia en cada frame.
• Análisis de datos: ordenamientos eficientes permiten agrupar, deduplicar y aplicar ventanas en millones de registros.

Con este contexto, el resto del curso se centra en algoritmos O(n log n) y en las técnicas para ajustarlos a distintos escenarios.