Ordenamiento por mezcla
De Wikipedia, la enciclopedia libre
El algoritmo de Ordenamiento por mezcla (Merge sort en inglés) es un algoritmo de ordenación estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).
[editar] Descripción
Fue desarrollado en 1945 por John Von Neumann.
A grandes rasgos, el algoritmo consiste en dividir en dos partes iguales el vector a ordenar, ordenar por separado cada una de las partes, y luego mezclar ambas partes, manteniendo la ordenación, en un solo vector ordenado.
A continuación se describe el algoritmo en pseudocódigo (se advierte de que no se incluyen casos especiales para vectores vacíos, etc.; una implementación en un lenguaje de programación real debería tener en cuenta estos detalles):
function mergesort(array A[0..n])
begin
array A1 := mergesort(A[0..(int(n / 2))])
array A2 := mergesort(A[int(1 + n / 2)..n])
return merge(A1, A2)
end
function merge(array A1[0..n1], array A2[0..n2])
begin
integer p1 := 0
integer p2 := 0
array R[0..(n1 + n2 - 1)]
while (p1 <= n1 or p2 <= n2):
if (p1 <= n1 and A1[p1] <= A2[p2]):
R[p1 + p2] := A1[p1]
p1 := p1 + 1
if (p2 <= n2 and A1[p1] > A2[p2]):
R[p1 + p2] := A2[p2]
p2 := p2 + 1
return R
end
[editar] Enlaces externos
- Animación de Algoritmo de Ordenamiento Merge Sort - Implementación en Java
