Overview
La ordenación por mezcla divide la lista a la mitad, ordena cada mitad recursivamente y luego las mezcla.
Analogy
Como organizar un escritorio desordenado: divide en dos pilas, ordena cada una y luego mezcla cuidadosamente las dos pilas ordenadas.
Step-by-step
- Caso base: lista de tamaño ≤ 1 ya está ordenada
- Divide la lista a la mitad
- Ordena recursivamente cada mitad
- Mezcla las dos mitades ordenadas con dos punteros
Visual
[8,3,5,1] → [8,3][5,1] → [3,8][1,5] → [1,3,5,8]
Common mistakes
- Olvidar el caso base de la recursión
- Lógica de mezcla incorrecta al combinar dos mitades
Practice questions
- Implementa merge sort de abajo a arriba de forma iterativa
- Cuenta inversiones durante la mezcla
Time
O(n log n) — siempre, peor/promedio/mejor caso
Space
O(n) — necesita espacio auxiliar