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

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?

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 ² ) .

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.

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 ₂ 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 ...

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.

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.

Solo como referencia, aquí hay una buena implementación de un tipo de fusión estable en el lugar . Complicado, pero no está mal.

Terminé implementando un tipo de fusión estable en el lugar y una clasificación rápida en el lugar estable en Java. Tenga en cuenta que la complejidad es O (n (log n) ^ 2)

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);
}

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.

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--;
    }
  }
}

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.

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;
}
}