Ordenamiento por mezcla

Keywords: Ordenamiento por mezcla, Algoritmo, Complejidad computacional, Cota superior asintótica, Idioma inglés

El algoritmo de Ordenamiento por mezcla (Merge sort en inglés) es un algoritmo de ordenación estable, recursivo, de complejidad O(n log n).

Descripción

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 ambos arrays, manteniendo la ordenación, en un solo array 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]):
   array A1 := mergesort(A[0..(int(n / 2))])
   array A2 := mergesort(A[int(1 + n / 2)..n])
   return merge(A1, A2)
 
 function merge(array A1[0..n1], array A2[0..n2]):
   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
 

Keywords: Ordenamiento por mezcla, Algoritmo, Complejidad computacional, Cota superior asintótica, Idioma inglés