¿Cómo ordenar en el lugar usando el algoritmo de clasificación de fusión?

244

Sé que la pregunta no es demasiado específica.

Todo lo que quiero es que alguien me diga cómo convertir una ordenación de fusión normal en una ordenación de fusión en el lugar (o una ordenación de fusión con una sobrecarga de espacio adicional constante).

Todo lo que puedo encontrar (en la red) son páginas que dicen "es demasiado complejo" o "fuera del alcance de este texto".

Las únicas formas conocidas de fusionarse en el lugar (sin espacio adicional) son demasiado complejas para reducirlas a un programa práctico. (tomado de aquí )

Incluso si es demasiado complejo, ¿cuál es el concepto básico de cómo ordenar la fusión en el lugar?

Lazer
fuente
Buena pregunta, la hice yo mismo al leer una pregunta de ayer: stackoverflow.com/questions/2566459/…
Chris Lercher
Aquí se describe un método bastante simple: xinok.wordpress.com/2014/08/17/…
Branko Dimitrijevic

Respuestas:

140

Knuth dejó esto como un ejercicio (Vol. 3, 5.2.5). Existen tipos de fusión en el lugar. Deben implementarse con cuidado.

Primero, la fusión ingenua en el lugar como se describe aquí no es la solución correcta. Reduce el rendimiento a O (N 2 ) .

La idea es ordenar parte de la matriz mientras se usa el resto como área de trabajo para la fusión.

Por ejemplo, como la siguiente función de fusión.

void wmerge(Key* xs, int i, int m, int j, int n, int w) {
    while (i < m && j < n)
        swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
    while (i < m)
        swap(xs, w++, i++);
    while (j < n)
        swap(xs, w++, j++);
}  

Toma la matriz xs, las dos sub-matrices ordenadas se representan como rangos [i, m)y [j, n)respectivamente. El área de trabajo comienza desde w. Compare con el algoritmo de fusión estándar dado en la mayoría de los libros de texto, este intercambia el contenido entre el subarreglo ordenado y el área de trabajo. Como resultado, el área de trabajo anterior contiene los elementos ordenados combinados, mientras que los elementos anteriores almacenados en el área de trabajo se mueven a las dos sub-matrices.

Sin embargo, hay dos restricciones que deben cumplirse:

  1. El área de trabajo debe estar dentro de los límites de la matriz. En otras palabras, debería ser lo suficientemente grande como para contener elementos intercambiados sin causar ningún error fuera de límite.
  2. El área de trabajo puede superponerse con cualquiera de las dos matrices ordenadas; sin embargo, debe asegurarse de que ninguno de los elementos no fusionados se sobrescriba.

Con este algoritmo de fusión definido, es fácil imaginar una solución, que puede clasificar la mitad de la matriz; La siguiente pregunta es, cómo lidiar con el resto de la parte sin clasificar almacenada en el área de trabajo como se muestra a continuación:

... unsorted 1/2 array ... | ... sorted 1/2 array ...

Una idea intuitiva es ordenar recursivamente otra mitad del área de trabajo, por lo tanto, solo hay 1/4 elementos que aún no se han ordenado.

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

El punto clave en esta etapa es que debemos fusionar los 1/4 elementos B ordenados con los 1/2 elementos A ordenados, tarde o temprano.

¿Queda el área de trabajo, que solo contiene 1/4 elementos, lo suficientemente grande como para fusionar A y B? Lamentablemente, no lo es.

Sin embargo, la segunda restricción mencionada anteriormente nos da una pista, de que podemos explotarla organizando el área de trabajo para que se superponga con cualquiera de los subconjuntos si podemos asegurar la secuencia de fusión de que los elementos no fusionados no se sobrescribirán.

En realidad, en lugar de ordenar la segunda mitad del área de trabajo, podemos ordenar la primera mitad y colocar el área de trabajo entre las dos matrices ordenadas de esta manera:

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

Esta configuración organiza efectivamente la superposición del área de trabajo con la sub-matriz A. Esta idea se propone en [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Práctico mergesort en el lugar ''. Revista nórdica de informática, 1996].

Entonces, lo único que queda es repetir el paso anterior, que reduce el área de trabajo de 1/2, 1/4, 1/8, ... Cuando el área de trabajo se vuelve lo suficientemente pequeña (por ejemplo, solo quedan dos elementos), podemos cambie a un tipo de inserción trivial para finalizar este algoritmo.

Aquí está la implementación en ANSI C basada en este documento.

void imsort(Key* xs, int l, int u);

void swap(Key* xs, int i, int j) {
    Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}

/* 
 * sort xs[l, u), and put result to working area w. 
 * constraint, len(w) == u - l
 */
void wsort(Key* xs, int l, int u, int w) {
    int m;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        imsort(xs, l, m);
        imsort(xs, m, u);
        wmerge(xs, l, m, m, u, w);
    }
    else
        while (l < u)
            swap(xs, l++, w++);
}

void imsort(Key* xs, int l, int u) {
    int m, n, w;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        w = l + u - m;
        wsort(xs, l, m, w); /* the last half contains sorted elements */
        while (w - l > 2) {
            n = w;
            w = l + (n - l + 1) / 2;
            wsort(xs, w, n, l);  /* the first half of the previous working area contains sorted elements */
            wmerge(xs, l, l + n - w, n, u, w);
        }
        for (n = w; n > l; --n) /*switch to insertion sort*/
            for (m = n; m < u && xs[m] < xs[m-1]; ++m)
                swap(xs, m, m - 1);
    }
}

Donde wmerge se define previamente.

El código fuente completo se puede encontrar aquí y la explicación detallada se puede encontrar aquí

Por cierto, esta versión no es el tipo de fusión más rápido porque necesita más operaciones de intercambio. Según mi prueba, es más rápido que la versión estándar, que asigna espacios adicionales en cada recursión. Pero es más lento que la versión optimizada, que duplica la matriz original por adelantado y la usa para una mayor fusión.

Larry LIU Xinyu
fuente
66
Knuth left this as an exercise (Vol 3, 5.2.5).se refiere a ex. 13. [40] Implementar el método interno de clasificación sugerido [en el cierre de esta sección], produciendo que clasifica datos aleatorios en O (N) unidades de mith tiempo sólo O (sqrt (n)) posiciones de memoria adicionales. ? ( 40 indica un problema bastante difícil o largo que tal vez sea adecuado como un proyecto de término en situaciones de clase. )
greybeard
44
Creo que la complejidad temporal del algoritmo in situ mencionado en el sitio penguin.ew es O (log n * n ^ 2). Dado que tenemos log n merges y cada fusión es del orden O (n ^ 2). ¿No es así?
code4fun
1
¿Este algoritmo sigue siendo estable y en n log n time?
Paul Stelian
1
@PaulStelian: no es estable. Los elementos en el área de trabajo se reorganizan de acuerdo con las operaciones de pedido de elementos en el área ordenada. Esto significa que los elementos del área de trabajo con valores iguales se reorganizarán para que ya no estén en su orden original.
rcgldr
1
@PaulStelian - Wiki tiene un artículo para ordenar la fusión de bloques , que como comentaste es estable. Funciona mejor si hay al menos 2 · sqrt (n) valores únicos, lo que les permite reordenarse para proporcionar áreas de trabajo de una matriz y permanecer estables.
rcgldr
59

Incluyendo su "gran resultado", este documento describe un par de variantes del tipo de fusión in situ (PDF):

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

Clasificación in situ con menos movimientos

Jyrki Katajainen, Tomi A. Pasanen

Se muestra que se puede ordenar una matriz de n elementos utilizando O (1) espacio adicional, movimientos de elementos O (n log n / log log n) y n log 2 n + O (n log log n) comparaciones. Este es el primer algoritmo de clasificación in situ que requiere movimientos de o (n log n) en el peor de los casos al tiempo que garantiza las comparaciones de O (n log n), pero debido a los factores constantes involucrados, el algoritmo es predominantemente de interés teórico.

Creo que esto también es relevante. Tengo una copia impresa por ahí, entregada por un colega, pero no la he leído. Parece cubrir la teoría básica, pero no estoy lo suficientemente familiarizado con el tema para juzgar cuán exhaustivamente:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

Óptima fusión estable

Antonios Symvonis

Este artículo muestra cómo fusionar de manera estable dos secuencias A y B de tamaños myn, m ≤ n, respectivamente, con asignaciones de O (m + n), comparaciones de O (mlog (n / m + 1) y usando solo una constante Cantidad de espacio adicional. Este resultado coincide con todos los límites inferiores conocidos ...

Steve Jessop
fuente
12

Realmente no es fácil ni eficiente, y sugiero que no lo haga a menos que realmente tenga que hacerlo (y probablemente no tenga que hacerlo a menos que esto sea tarea ya que las aplicaciones de la fusión in situ son en su mayoría teóricas). ¿No puedes usar quicksort en su lugar? Quicksort será más rápido de todos modos con algunas optimizaciones más simples y su memoria adicional es O (log N) .

De todos modos, si debes hacerlo, entonces debes hacerlo. Esto es lo que encontré: uno y dos . No estoy familiarizado con el tipo de fusión in situ, pero parece que la idea básica es usar rotaciones para facilitar la fusión de dos matrices sin usar memoria adicional.

Tenga en cuenta que esto es más lento incluso que el clásico tipo de fusión que no está en su lugar.

IVlad
fuente
99
Quicksort no es estable. Eso realmente importa para una gran cantidad de código de producción.
Donal Fellows
77
quicksort puede ser estable, y iirc merge sort no es necesariamente estable si está en su lugar
jk.
44
@jk: Quicksort no es estable; su velocidad se deriva de eso y no deberías intentar reclamar lo contrario. Es una muy buena compensación. Sí, es posible asociar el índice original con el resto de la clave para que nunca tenga dos elementos iguales, dando una clasificación estable; eso tiene un costo necesario de espacio extra (lineal en el número de elementos) porque no se puede mantener el orden relativo de los elementos "equivalentes" sin recurrir a movimientos de elementos adicionales que destruyen el rendimiento.
Donal Fellows
44
Quicksort también tiene un O (n ^ 2) peor caso para entrada especialmente diseñada
HoboBen
44
@DonalFellows: jk tiene toda la razón; quicksort PUEDE implementarse para ser estable, sin costo de espacio adicional. Revisa Wikipedia.
Oxidado
10

El paso crítico es conseguir la fusión. esté en su lugar. No es tan difícil como lo hacen esas fuentes, pero pierdes algo cuando lo intentas.

Mirando un paso de la fusión:

[... lista ordenada ... | x ... lista- A ... | y ... lista- B ...]

Sabemos que la ordenada secuencia es menos de todo lo demás, que x es menor que todo lo demás en A , y que y es menos de todo lo demás en B . En el caso de que x sea ​​menor o igual que y , simplemente mueva su puntero al comienzo de A en uno. En el caso de que y sea ​​menor que x , debe barajar y pasar todo A para ordenar . El último paso es lo que lo hace costoso (excepto en casos degenerados).

En general, es más barato (especialmente cuando las matrices solo contienen palabras individuales por elemento, por ejemplo, un puntero a una cadena o estructura) para intercambiar algo de espacio por tiempo y tener una matriz temporal separada entre las que puede ordenar de un lado a otro.

Compañeros de Donal
fuente
55
Su fusión en el lugar tiene O (m n) la peor complejidad, donde m es el tamaño A yn es el tamaño B. Este es el caso cuando el primer elemento en A es más grande que el último elemento en B. La complejidad se puede mejorar a O (k log (k) + m + n), donde k = min (m, n) agregando un montón entre A y B. Este montón debe contener elementos de A, que son más grandes que los elementos restantes en B, pero más pequeños que los elementos restantes en A. Si A se agota primero, entonces el montón debe moverse al final de B. De lo contrario, el montón se debe mover al principio de A. Luego, los elementos del montón se deben desplegar en su lugar e invertir para completar la fusión.
valyala
2
@valyala Tenga en cuenta que cuando se usa un montón, el orden ya no es estable. Además, si usa un montón, puede ir con la ordenación del montón en lugar de la combinación.
martinkunev
4

Un ejemplo de mergesort sin buffer en C.

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static void reverse_(int* a, int* b)
{
    for ( --b; a < b; a++, b-- )
       SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       reverse_(a, b);
       reverse_(b, c);
       reverse_(a, c);
     }
    return a + (c - b);
}

static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid < key)
          a = mid + 1, i--;
     }
    return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid <= key)
          a = mid + 1, i--;
     }
    return a;
}

static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 == 0 || n2 == 0)
       return;
    if (n1 == 1 && n2 == 1)
     {
       if (*b < *a)
          SWAP(int, *a, *b);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b);
       ip_merge_(b, q, c);
     }
}

void mergesort(int* v, int n)
{
    if (n > 1)
     {
       int h = n/2;
       mergesort(v, h); mergesort(v+h, n-h);
       ip_merge_(v, v+h, v+n);
     }
}

Un ejemplo de mergesort adaptativo (optimizado).

Agrega código de soporte y modificaciones para acelerar la fusión cuando hay disponible un búfer auxiliar de cualquier tamaño (aún funciona sin memoria adicional). Utiliza la fusión hacia adelante y hacia atrás, la rotación del anillo, la fusión y clasificación de secuencias pequeñas y la fusión iterativa.

#include <stdlib.h>
#include <string.h>

static int* copy_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (a != out)
       memcpy(out, a, count*sizeof(int));
    return out + count;
}
static int* copy_backward_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (b != out)
       memmove(out - count, a, count*sizeof(int));
    return out - count;
}

static int* merge_(const int* a1, const int* b1, const int* a2,
  const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *out++ = (*a1 <= *a2) ? *a1++ : *a2++;
    return copy_(a2, b2, copy_(a1, b1, out));
}
static int* merge_backward_(const int* a1, const int* b1,
  const int* a2, const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2;
    return copy_backward_(a1, b1, copy_backward_(a2, b2, out));
}

static unsigned int gcd_(unsigned int m, unsigned int n)
{
    while ( n != 0 )
     {
       unsigned int t = m % n;
       m = n;
       n = t;
     }
    return m;
}
static void rotate_inner_(const int length, const int stride,
  int* first, int* last)
{
    int* p, * next = first, x = *first;
    while ( 1 )
     {
       p = next;
       if ((next += stride) >= last)
          next -= length;
       if (next == first)
          break;
       *p = *next;
     }
    *p = x;
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       int n1 = c - a;
       int n2 = b - a;

       int* i = a;
       int* j = a + gcd_(n1, n2);

       for ( ; i != j; i++ )
          rotate_inner_(n1, n2, i, c);
     }
    return a + (c - b);
}

static void ip_merge_small_(int* a, int* b, int* c)
/* inplace merge.
 * @note faster for small sequences. */
{
    while ( a != b && b != c )
       if (*a <= *b)
          a++;
       else
        {
          int* p = b+1;
          while ( p != c && *p < *a )
             p++;
          rotate_(a, b, p);
          b = p;
        }
}
static void ip_merge_(int* a, int* b, int* c, int* t, const int ts)
/* inplace merge.
 * @note works with or without additional memory. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 <= n2 && n1 <= ts)
     {
       merge_(t, copy_(a, b, t), b, c, a);
     }
    else if (n2 <= ts)
     {
       merge_backward_(a, b, t, copy_(b, c, t), c);
     }
    /* merge without buffer. */
    else if (n1 + n2 < 48)
     {
       ip_merge_small_(a, b, c);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b, t, ts);
       ip_merge_(b, q, c, t, ts);
     }
}
static void ip_merge_chunk_(const int cs, int* a, int* b, int* t,
  const int ts)
{
    int* p = a + cs*2;
    for ( ; p <= b; a = p, p += cs*2 )
       ip_merge_(a, a+cs, p, t, ts);
    if (a+cs < b)
       ip_merge_(a, a+cs, b, t, ts);
}

static void smallsort_(int* a, int* b)
/* insertion sort.
 * @note any stable sort with low setup cost will do. */
{
    int* p, * q;
    for ( p = a+1; p < b; p++ )
     {
       int x = *p;
       for ( q = p; a < q && x < *(q-1); q-- )
          *q = *(q-1);
       *q = x;
     }
}
static void smallsort_chunk_(const int cs, int* a, int* b)
{
    int* p = a + cs;
    for ( ; p <= b; a = p, p += cs )
       smallsort_(a, p);
    smallsort_(a, b);
}

static void mergesort_lower_(int* v, int n, int* t, const int ts)
{
    int cs = 16;
    smallsort_chunk_(cs, v, v+n);
    for ( ; cs < n; cs *= 2 )
       ip_merge_chunk_(cs, v, v+n, t, ts);
}

static void* get_buffer_(int size, int* final)
{
    void* p = NULL;
    while ( size != 0 && (p = malloc(size)) == NULL )
       size /= 2;
    *final = size;
    return p;
}
void mergesort(int* v, int n)
{
    /* @note buffer size may be in the range [0,(n+1)/2]. */
    int request = (n+1)/2 * sizeof(int);
    int actual;
    int* t = (int*) get_buffer_(request, &actual);

    /* @note allocation failure okay. */
    int tsize = actual / sizeof(int);
    mergesort_lower_(v, n, t, tsize);
    free(t);
}
Johnny Cage
fuente
2
Escribiste esto? ¿Cómo supera las dificultades expresadas en las otras respuestas? ¿Cuál es su tiempo de ejecución?
Thomas Ahle
Esto está adaptado de mi propia biblioteca personalizada , pero no creé estos algoritmos si eso es lo que estás preguntando. El crecimiento es O (n (log n) ^ 2) sin memoria auxiliar; O (n log n) con búfer completo. Esto trata de ser una implementación práctica, y está estructurado para mostrar algoritmos constituyentes.
Johnny Cage
¿Por qué necesita recursividad o buffer adicional para fusionar dos listas ordenadas? Creo que se puede hacer moviendo los dos punteros hacia adelante e intercambiando si la izquierda es más grande que la derecha.
Jack
3

Esta respuesta tiene un ejemplo de código , que implementa el algoritmo descrito en el documento Practical In-Place Merging por Bing-Chao Huang y Michael A. Langston. Tengo que admitir que no entiendo los detalles, pero la complejidad dada del paso de fusión es O (n).

Desde una perspectiva práctica, existe evidencia de que las implementaciones in situ puras no funcionan mejor en escenarios del mundo real. Por ejemplo, el estándar C ++ define std :: inplace_merge , que es como su nombre implica una operación de fusión in situ.

Suponiendo que las bibliotecas de C ++ suelen estar muy bien optimizadas, es interesante ver cómo se implementa:

1) libstdc ++ (parte de la base del código GCC): std :: inplace_merge

La implementación delega a __inplace_merge , que esquiva el problema al tratar de asignar un búfer temporal:

typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __len1 + __len2);

if (__buf.begin() == 0)
  std::__merge_without_buffer
    (__first, __middle, __last, __len1, __len2, __comp);
else
  std::__merge_adaptive
   (__first, __middle, __last, __len1, __len2, __buf.begin(),
     _DistanceType(__buf.size()), __comp);

De lo contrario, recurre a una implementación ( __merge_without_buffer ), que no requiere memoria adicional, pero ya no se ejecuta en tiempo O (n).

2) libc ++ (parte de la base del código Clang): std :: inplace_merge

Se ve similar. Delega a una función , que también intenta asignar un búfer . Dependiendo de si tiene suficientes elementos, elegirá la implementación. La función de reserva de memoria constante se llama __buffered_inplace_merge .

Tal vez incluso el respaldo todavía sea tiempo O (n), pero el punto es que no usan la implementación si hay memoria temporal disponible.


Tenga en cuenta que el estándar C ++ brinda explícitamente a las implementaciones la libertad de elegir este enfoque al reducir la complejidad requerida de O (n) a O (N log N):

Complejidad: Exactamente comparaciones N-1 si hay suficiente memoria adicional disponible. Si la memoria es insuficiente, O (N log N) comparaciones.

Por supuesto, esto no puede tomarse como una prueba de que el espacio constante en el lugar se fusiona en el tiempo O (n) nunca debe usarse. Por otro lado, si fuera más rápido, las bibliotecas optimizadas de C ++ probablemente cambiarían a ese tipo de implementación.

Philipp Claßen
fuente
2

Esta es mi versión C:

void mergesort(int *a, int len) {
  int temp, listsize, xsize;

  for (listsize = 1; listsize <= len; listsize*=2) {
    for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
      merge(& a[i], listsize, listsize);
    }
  }

  listsize /= 2;

  xsize = len % listsize;
  if (xsize > 1)
    mergesort(& a[len-xsize], xsize);

  merge(a, listsize, xsize);
}

void merge(int *a, int sizei, int sizej) {
  int temp;
  int ii = 0;
  int ji = sizei;
  int flength = sizei+sizej;

  for (int f = 0; f < (flength-1); f++) {
    if (sizei == 0 || sizej == 0)
      break;

    if (a[ii] < a[ji]) {
      ii++;
      sizei--;
    }
    else {
      temp = a[ji];

      for (int z = (ji-1); z >= ii; z--)
        a[z+1] = a[z];  
      ii++;

      a[f] = temp;

      ji++;
      sizej--;
    }
  }
}
Dylan Nissley
fuente
Tenga en cuenta que esta implementación lleva Θ (n ^ 2 log n) tiempo en el peor de los casos (matriz invertida).
martinkunev
1

Existe una implementación relativamente simple de ordenamiento por fusión en el lugar utilizando la técnica original de Kronrod pero con una implementación más simple. Un ejemplo ilustrativo que ilustra esta técnica se puede encontrar aquí: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

También hay enlaces a análisis teóricos más detallados del mismo autor asociados con este enlace.

Calbert
fuente
este enlace da como resultado un 403
Charlotte Tan
3
El enlace es fijo. La documentación allí es críptica hasta el punto de obtuso. Tengo la impresión de que hay una idea interesante allí, pero no se presenta ningún algoritmo, solo un conjunto de diagramas y algunas descripciones bastante débiles. No pude vincular las descripciones débiles a los diagramas de una manera interesante, así que me di por vencido.
Ira Baxter
-6

Acabo de probar el algoritmo de fusión para la ordenación por fusión en JAVA usando el algoritmo de ordenación por inserción, siguiendo los siguientes pasos.
1) Dos arreglos ordenados están disponibles.
2) Compare los primeros valores de cada matriz; y coloque el valor más pequeño en la primera matriz.
3) Coloque el valor más grande en la segunda matriz utilizando el orden de inserción (transversal de izquierda a derecha).
4) Luego, vuelva a comparar el segundo valor de la primera matriz y el primer valor de la segunda matriz, y haga lo mismo. Pero cuando ocurre el intercambio, hay alguna pista sobre la omisión de comparar los elementos adicionales, pero solo se requiere el intercambio.

He hecho alguna optimización aquí; para mantener comparaciones menores en el tipo de inserción.
El único inconveniente que encontré con estas soluciones es que necesita un mayor intercambio de elementos de la matriz en la segunda matriz.

p.ej)

Primero___Array: 3, 7, 8, 9

Segunda matriz: 1, 2, 4, 5

Entonces 7, 8, 9 hace que la segunda matriz intercambie (se mueva hacia la izquierda por uno) todos sus elementos por uno cada vez para colocarse en el último.

Entonces, la suposición aquí es el intercambio de elementos es insignificante en comparación con la comparación de dos elementos.

https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

package sorting;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
    int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
    mergeSort(array, 0, array.length -1);
    System.out.println(Arrays.toString(array));

    int[] array1 = {4, 7, 2};
    System.out.println(Arrays.toString(array1));
    mergeSort(array1, 0, array1.length -1);
    System.out.println(Arrays.toString(array1));
    System.out.println("\n\n");

    int[] array2 = {4, 7, 9};
    System.out.println(Arrays.toString(array2));
    mergeSort(array2, 0, array2.length -1);
    System.out.println(Arrays.toString(array2));
    System.out.println("\n\n");

    int[] array3 = {4, 7, 5};
    System.out.println(Arrays.toString(array3));
    mergeSort(array3, 0, array3.length -1);
    System.out.println(Arrays.toString(array3));
    System.out.println("\n\n");

    int[] array4 = {7, 4, 2};
    System.out.println(Arrays.toString(array4));
    mergeSort(array4, 0, array4.length -1);
    System.out.println(Arrays.toString(array4));
    System.out.println("\n\n");

    int[] array5 = {7, 4, 9};
    System.out.println(Arrays.toString(array5));
    mergeSort(array5, 0, array5.length -1);
    System.out.println(Arrays.toString(array5));
    System.out.println("\n\n");

    int[] array6 = {7, 4, 5};
    System.out.println(Arrays.toString(array6));
    mergeSort(array6, 0, array6.length -1);
    System.out.println(Arrays.toString(array6));
    System.out.println("\n\n");

    //Handling array of size two
    int[] array7 = {7, 4};
    System.out.println(Arrays.toString(array7));
    mergeSort(array7, 0, array7.length -1);
    System.out.println(Arrays.toString(array7));
    System.out.println("\n\n");

    int input1[] = {1};
    int input2[] = {4,2};
    int input3[] = {6,2,9};
    int input4[] = {6,-1,10,4,11,14,19,12,18};
    System.out.println(Arrays.toString(input1));
    mergeSort(input1, 0, input1.length-1);
    System.out.println(Arrays.toString(input1));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input2));
    mergeSort(input2, 0, input2.length-1);
    System.out.println(Arrays.toString(input2));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input3));
    mergeSort(input3, 0, input3.length-1);
    System.out.println(Arrays.toString(input3));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input4));
    mergeSort(input4, 0, input4.length-1);
    System.out.println(Arrays.toString(input4));
    System.out.println("\n\n");
}

private static void mergeSort(int[] array, int p, int r) {
    //Both below mid finding is fine.
    int mid = (r - p)/2 + p;
    int mid1 = (r + p)/2;
    if(mid != mid1) {
        System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ "  for p:"+p+"  r:"+r);
    }

    if(p < r) {
        mergeSort(array, p, mid);
        mergeSort(array, mid+1, r);
//      merge(array, p, mid, r);
        inPlaceMerge(array, p, mid, r);
        }
    }

//Regular merge
private static void merge(int[] array, int p, int mid, int r) {
    int lengthOfLeftArray = mid - p + 1; // This is important to add +1.
    int lengthOfRightArray = r - mid;

    int[] left = new int[lengthOfLeftArray];
    int[] right = new int[lengthOfRightArray];

    for(int i = p, j = 0; i <= mid; ){
        left[j++] = array[i++];
    }

    for(int i = mid + 1, j = 0; i <= r; ){
        right[j++] = array[i++];
    }

    int i = 0, j = 0;
    for(; i < left.length && j < right.length; ) {
        if(left[i] < right[j]){
            array[p++] = left[i++];
        } else {
            array[p++] = right[j++];
        }
    }
    while(j < right.length){
        array[p++] = right[j++];
    } 
    while(i < left.length){
        array[p++] = left[i++];
    }
}

//InPlaceMerge no extra array
private static void inPlaceMerge(int[] array, int p, int mid, int r) {
    int secondArrayStart = mid+1;
    int prevPlaced = mid+1;
    int q = mid+1;
    while(p < mid+1 && q <= r){
        boolean swapped = false;
        if(array[p] > array[q]) {
            swap(array, p, q);
            swapped = true;
        }   
        if(q != secondArrayStart && array[p] > array[secondArrayStart]) {
            swap(array, p, secondArrayStart);
            swapped = true;
        }
        //Check swapped value is in right place of second sorted array
        if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) {
            prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced);
        }
        p++;
        if(q < r) {     //q+1 <= r) {
            q++;
        }
    }
}

private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) {
    int i = secondArrayStart;
    for(; i < array.length; i++) {
        //Simply swap till the prevPlaced position
        if(secondArrayStart < prevPlaced) {
            swap(array, secondArrayStart, secondArrayStart+1);
            secondArrayStart++;
            continue;
        }
        if(array[i] < array[secondArrayStart]) {
            swap(array, i, secondArrayStart);
            secondArrayStart++;
        } else if(i != secondArrayStart && array[i] > array[secondArrayStart]){
            break;
        }
    }
    return secondArrayStart;
}

private static void swap(int[] array, int m, int n){
    int temp = array[m];
    array[m] = array[n];
    array[n] = temp;
}
}
Kanagavelu Sugumar
fuente
3
Es a la vez O (n ^ 2) y también muy ilegible (debido a los errores de sintaxis ocasionales y el estilo inconsistente / pobre)
glaba