Ordenamiento por mezcla (merge sort)
Merge sort
- Fecha
- 1945-1948 · fiabilidad alta
- Lugar
- Princeton, Nueva Jersey, Estados Unidos
- Autoría
- John von Neumann
- Ámbito
- Saber y símbolos
Qué es
John von Neumann ideó en 1945 el algoritmo de ordenamiento por mezcla (merge sort), que divide una lista en partes cada vez más pequeñas, las ordena por separado y las combina de nuevo, logrando un rendimiento O(n log n) muy superior al de los métodos de ordenación más simples.
Von Neumann programó una versión para el EDVAC en 1945; una descripción detallada y su análisis aparecieron en un informe de Goldstine y von Neumann en 1948.
A qué dio paso
- paradigma de algoritmos de tipo 'divide y vencerás'
- uno de los primeros algoritmos analizados formalmente para computadoras digitales
- base de implementaciones de ordenación estable usadas hoy en lenguajes de programación