Ordenamiento por mezcla

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).

Descripción

Fue desarrollado en 1945 por John Von Neumann.

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

1. Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

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[x..y])
begin
  if (x-y > 1)):
    array A1 := mergesort(A[x..(int( x+y / 2))])
    array A2 := mergesort(A[int(1+(x+y / 2))..y])
    return merge(A1, A2)
  else:
    return A
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

Implementaciones

Perl

sub mergesort {
    mergesort_recursivo ($_[0], 0, $#{ $_[0] });  # Recibimos una referencia a un array
}

sub mergesort_recursivo {
    my ( $array, $primero, $ultimo ) = @_;

    if ( $ultimo > $primero ) {
        local $^W = 0;              # Quitamos el aviso de exceso de recursión

        my $mitad = int(( $ultimo + $primero ) / 2);
        mergesort_recursivo( $array, $primero, $mitad );
        mergesort_recursivo( $array, $mitad + 1, $ultimo );
        merge( $array, $primero, $mitad, $ultimo );
    }
}

my @work; # Una variable global.

sub merge {
    my ( $array, $primero, $mitad, $ultimo ) = @_;
    my $n = $ultimo - $primero + 1;

    # Inicializa @work con elementos importantes del array
    for ( my $i = $primero, my $j = 0; $i <= $ultimo; ) {
        $work[ $j++ ] = $array->[ $i++ ];
    }

    # Ahora hace la verdadera mezcla. Atraviesa el array
    # y copia los elementos en orden inverso al array original
    # $i es el índice del resultado de la mezcla, $j es el índice en
    # la primera mitad de la copia de trabajo, $k el índice de la segunda mitad.

    $mitad = int(($primero + $ultimo) / 2) if $mitad > $ultimo;
    my $n1 = $mitad - $primero + 1;      # El tamaño de la primera mitad.

    for ( my $i = $primero, my $j = 0, my $k = $n1;
          $i <= $ultimo;
          $i++ ) {

            $array->[ $i ] =
                              $j < $n1
                           &&
                              ( $k == $n || $work[ $j ] < $work[ $k ] ) 
                              ? $work[ $j++ ]
                              : $work[ $k++ ]
                           ;
    }
}

C

void mezclar(int arreglo1[], int n1, int arreglo2[], int n2, int arreglo3[])
{
    int x1=0, x2=0, x3=0;

    while (x1<n1 && x2<n2) {
  	if (arreglo1[x1]<arreglo2[x2]) {
  	    arreglo3[x3] = arreglo1[x1];
            x1++;
  	} else {
  	    arreglo3[x3] = arreglo2[x2];
 	    x2++;
  	}
  	x3++;
    }
	x1=0;x2=0;x3=0; 
    while (x1<n1) {
  	arreglo3[x3] = arreglo1[x1];
 	x1++;
        x3++;
    }
    while (x2<n2) {
  	arreglo3[x3] = arreglo2[x2];
 	x2++;
 	x3++
    }
}

void mezcla(int vector[], int n)
{
    int *vector1, *vector2, n1, n2,x,y;
    if (n>1)
    {
  	if (n%2 == 0)
  	    n1=n2=(int) n / 2;
  	else
        {
  	    n1=(int) n / 2;n2=n1+1;
  	}
  	vector1=(int *) malloc(sizeof(int)*n1);
        vector2=(int *) malloc(sizeof(int)*n2);
        for(x=0;x<n1;x++)
  	    vector1[x]=vector[x];
        for(y=0;y<n2;x++,y++)
  	    vector2[y]=vector[x];
        mezcla(vector1, n1);
        mezcla(vector2,n2);
        mezclar(vector1, n1, vector2, n2, vector);
        free(vector1);
        free(vector2);
    } 	 
}

int main(){
    int i, vector[] = {2,3,5,7,2,6,1,5,8,3,2};
	
    mezcla(vector,12);
    
    for(i=0;i<12;i++)
        printf("%i,\n", vector[i]);
		
    return 0;
}

C++

// En el código usamos la clase vector (#include <vector>) para crear los vectores,
// obviamente funciona igual de bien si se utilizan los arrays tipo C: TIPO V[]
template <class T>
void fusiona(vector<T>& v, int ini, int med, int fin) {
    vector<T> aux(fin - ini + 1);
    int i = ini; // Índice de la parte izquierda
    int j = med + 1; // Índice de la parte derecha
    int k = 0; // Índice del vector aux
    
    
    /* Mientras ninguno de los indices llegue a su fin vamos realizando
       comparaciones. El elemento más pequeño se copia al vector aux */
    while (i <= med && j <= fin) {
        if (v[i] < v[j]) {
            aux[k] = v[i];
            i++;
        }
        else {
            aux[k] = v[j];
            j++;
        }
        k++;
    }
    
    /* Uno de los dos sub-vectores ya ha sido copiado del todo, simplemente
       debemos copiar todo el sub-vector que nos falte */
    while (i <= med) {
        aux[k] = v[i];
        i++;
        k++;
    }
    
    while (j <= fin) {
        aux[k] = v[j];
        j++;
        k++;
    }
    
    /* Copiamos los elementos ordenados de aux al vector original v */
    for (int n = 0; n < aux.size(); ++n) v[ini + n] = aux[n];
}

template <class T>
void merge_sort(vector<T>& v, int ini, int fin) {
    /* Si ini = fin el sub-vector es de un solo elemento y, por lo tanto
       ya está ordenado por definición */
    if (ini < fin) {
/*Considerar que el valor de med siempre es redondeado hacia abajo.*/
        int med = (ini + fin)/2;
        merge_sort(v, ini, med);
        merge_sort(v, med + 1, fin);
        fusiona(v, ini, med, fin);
    }
}

Visual Basic

Option Base 1

Private Sub Form_Load()
    Dim N As Integer
    N = InputBox("Tamaño del arreglo: ", "MergeSort")
    ReDim A(N) As Integer
    For i = 1 To N
        A(i) = CInt(InputBox("Elemento " & i & ":"))
    Next
    MergeSort N, A, 1, N
    Dim Arreglo As String
    For j = 1 To N
        Arreglo = Arreglo & A(j) & " "
    Next
    MsgBox Arreglo, vbInformation, "MergeSort"
    Unload Me
End Sub

Sub Merge(N As Integer, ByRef A() As Integer, ini As Integer, med As Integer, fin As Integer)
    Dim n1 As Integer
    n1 = med - ini + 1
    Dim n2 As Integer
    n2 = fin - med
    ReDim L(n1 + 1) As Integer
    ReDim R(n2 + 1) As Integer
    For z = 1 To n1
        L(z) = A(ini + z - 1)
    Next
    For z = 1 To n2
        R(z) = A(med + z)
    Next
    L(n1 + 1) = 32767
    R(n2 + 1) = 32767
    Dim i As Integer
    Dim j As Integer
    i = 1
    j = 1
    For k = ini To fin
        If L(i) <= R(j) Then
            A(k) = L(i)
            i = i + 1
        ElseIf L(i) > R(j) Then
            A(k) = R(j)
            j = j + 1
        End If
    Next
End Sub

Sub MergeSort(N As Integer, ByRef A() As Integer, inicio As Integer, fin As Integer)
    If inicio < fin Then
        Dim medio As Integer
        medio = (inicio + fin) \ 2
        MergeSort N, A, inicio, medio
        MergeSort N, A, medio + 1, fin
        Merge N, A, inicio, medio, fin
    End If
End Sub

Java

public class MergeSort{
     private int A[];
     public int[] OrdenaMerge(int[] L) {
        int n = L.length;

        if (n > 1){
            int m = (int) (Math.ceil(n/2.0));
            int [] L1 = new int[m];
            int [] L2 = new int[n-m];

            for (int i = 0; i < m; i++){
                L1[i] = L[i];
            }
            for (int i = m; i < n; i++){
                L2[i-m] = L[i];
            }
            L = merge(OrdenaMerge(L1), OrdenaMerge(L2));
        }
        return L;
    }

    public int[] eliminar(int [] l){
        int [] L = new int[l.length-1];
        for(int i = 1; i < l.length; i++){
            L[i-1] = l[i];
        }
        return L;
    }

    public int[] merge(int[] L1, int[] L2) {
         int[] L = new int[L1.length+L2.length];
         int i = 0;
         while ((L1.length != 0) && (L2.length != 0)) {
             if (L1[0] < L2[0]){
                 L[i++] = L1[0];
                 L1 = eliminar(L1);
                 if (L1.length == 0){
                     while (L2.length != 0) {
                         L[i++] = L2[0];
                         L2 = eliminar(L2);
                     }
                 }
             }
             else{
                 L[i++] = L2[0];
                 L2 = eliminar(L2);
                 if (L2.length == 0) {
                    while (L1.length != 0) {
                         L[i++] = L1[0];
                         L1 = eliminar(L1);
                    }
                 }
             }
         }
         return L;
    }

    public void generarNumeros(){
        Random ran = new Random();
        int x;
        for(int i = 0; i < A.length; i++){
            x = (int)(ran.nextDouble()*10000);
            A[i] = x;
        }
    }
    
    public void imprimir(){
        for(int i = 0; i < A.length; i++){
            System.out.println(A[i]);
        }
    }
    
    public int[] getA(){
        return A;
    }
    
    public void setA(int []A){
        this.A = A;
    }
}

Optimizando merge sort

En los ordenadores modernos, el principio de localidad puede ser primordial en la optimización de software, porque se usan jerarquías de memoria multi-nivel. Se han propuesto versiones de cache-consciente del algoritmo de ordenación por mezcla, cuyas operaciones han sido específicamente escogidas para minimizar el movimiento de entrada y salida de páginas de la memoria caché de la máquina. Por ejemplo, el algorimo "tiled merge sort" deja de particionar subarrays cuando se han alcanzado subarrays de tamaño S, donde S es el número de elementos que caben en una única página en memoria. Cada uno de esos subarrays se ordenan con un algorimo de ordenación in-situ, para evitar intercambios en memoria, y entonces se termina con el algoritmo de ordenamiento por mezcla en su versión recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento en máquinas que se benefician de la optimización caché.

M.A. Kronrod sugirió en 1969 una versión alternativa del algoritmo de ordenamiento por mezcla que usaba espacio adicional constante. Este algoritmo fue refinado por Katajainen, Pasanen y Teuhola.

Comparación con otros algoritmos de ordenamiento

Aunque heapsort tiene los mismos límites de tiempo que merge sort, requiere sólo Θ(1) espacio auxiliar en lugar del Θ(n) de merge sort, y es a menudo más rápido en implementaciones prácticas. Quicksort, sin embargo, es considerado por mucho como el más rápido algoritmo de ordenamiento de propósito general. En el lado bueno, merge sort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento. Merge sort es a menudo la mejor opción para ordenar una lista enlazada: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera Θ(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el acceso aleatorio hace que otros algoritmos (como quicksort) den un bajo rendimiento, y para otros (como heapsort) sea algo imposible.

Para Perl 5.8, merge sort es el algoritmo de ordenamiento por defecto (lo era quicksort en versiones anteriores de Perl). En Java los métodos de ordenación de Arrays usan merge sort o una modificación de quicksort dependiendo de los tipos de datos y por cuestiones de eficiencia cambian a ordenamiento por inserción cuando se están ordenando menos de siete elementos en el array.

Enlaces externos

Implementaciones

• Sort::Merge Módulo Perl en CPAN
• File::MergeSort Módulo Perl en CPAN