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 externo 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] Implementaciones

El algoritmo Ordenamiento por mezcla (Merge Sort) en 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++ ]
                           ;
    }
}

En 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 and 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) {
        int med = (ini + fin)/2;
        merge_sort(v, ini, med);
        merge_sort(v, med + 1, fin);
        fusiona(v, ini, med, fin);
    }
}