GUÍA 23-11-26 Estructuras de Datos

CN122 · lunes 23/11/2026 · 13:00-14:15 · Sesión 29

Métodos de ordenamiento sobre arreglos (2/3)

DIVIDE Y VENCERÁS

Se parte el problema en subproblemas del mismo tipo, se resuelven recursivamente y se combinan. Es la estrategia que rompe la barrera de O(n²).

MERGE SORT

1. Dividir el arreglo por la mitad.

2. Ordenar recursivamente cada mitad.

3. Mezclar las dos mitades ordenadas.

• O(n log n) garantizado en todos los casos, sin excepción.
• Estable.
• Requiere O(n) de memoria adicional para la mezcla; no es in situ.

La mezcla es exactamente el algoritmo de combinar dos listas ordenadas de la sesión 17. El nivel de recursión es log n y cada nivel cuesta O(n), de ahí el producto.

QUICKSORT

1. Elegir un pivote.

2. Particionar: menores a la izquierda, mayores a la derecha.

3. Ordenar recursivamente cada lado.

• O(n log n) en promedio; O(n²) en el peor caso, cuando el pivote es siempre el extremo.
• In situ salvo la pila de recursión; no estable.
• En la práctica es el más rápido de todos por su excelente localidad de caché.

ELECCIÓN DEL PIVOTE

• Primero o último: sencillo, pero degenera con datos ya ordenados.
• Mediana de tres: toma el medio de primero, central y último. Es lo habitual.
• Aleatorio: hace improbable el peor caso sin importar la entrada.

MERGE O QUICK

Quicksort para arreglos en memoria, por velocidad. Merge sort cuando se necesita estabilidad garantizada o cuando los datos no caben en RAM, porque se adapta bien al ordenamiento externo por bloques.

PRÁCTICA

Implementar ambos y medir tiempos contra los cuadráticos con 10⁵ elementos; provocar el peor caso de quicksort.