¿Qué es cierto sobre merge sort?
Opciones
- Ordena in place con memoria O(1), pero no es estable
- Es estable, siempre O(n log n), y necesita O(n) de espacio extra (Opción correcta)
- Su peor caso es O(n²) cuando la entrada está casi ordenada
- Solo funciona con linked lists, nunca con arrays normales
Respuesta
Estable, O(n log n) en todos los casos, O(n) de espacio extra en arrays
Por qué
Merge sort divide la lista por la mitad hasta quedarse con elementos sueltos y luego fusiona las mitades ordenadas. Cada nivel cuesta O(n) y hay log n niveles: O(n log n), siempre.
Fusionar necesita un array temporal: O(n) de memoria extra.
Es estable: los elementos iguales conservan su orden original, algo que importa cuando ordenas por un campo y luego por otro.
Recuerda
Merge sort = siempre O(n log n), estable, necesita memoria extra.