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