Como classificar no local usando o algoritmo de classificação de mesclagem?

Eu sei que a pergunta não é muito específica.

Tudo o que quero é que alguém me diga como converter uma classificação de mesclagem normal em uma classificação de mesclagem no local (ou uma classificação de mesclagem com sobrecarga de espaço extra constante).

Tudo o que posso encontrar (na rede) são páginas dizendo "é muito complexo" ou "fora do escopo deste texto".

As únicas maneiras conhecidas de mesclar no local (sem espaço extra) são muito complexas para serem reduzidas a programas práticos. (tirada daqui )

Mesmo que seja muito complexo, qual é o conceito básico de como fazer a mesclagem se encaixar?

Knuth deixou isso como um exercício (Vol 3, 5.2.5). Existem classificações de mesclagem no local. Eles devem ser implementados com cuidado.

Primeiro, a mesclagem ingênua no local, como descrita aqui, não é a solução certa. Reduz o desempenho para O (N ² ) .

A idéia é classificar parte da matriz enquanto usa o restante como área de trabalho para mesclagem.

Por exemplo, como a seguinte função de mesclagem.

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

Leva a matriz xs, as duas sub-matrizes ordenadas são representadas como intervalos [i, m)e [j, n)respectivamente. A área de trabalho começa em w. Comparado com o algoritmo de mesclagem padrão fornecido na maioria dos livros, este troca o conteúdo entre a sub-matriz classificada e a área de trabalho. Como resultado, a área de trabalho anterior contém os elementos classificados mesclados, enquanto os elementos anteriores armazenados na área de trabalho são movidos para as duas sub-matrizes.

No entanto, existem duas restrições que devem ser atendidas:

1. A área de trabalho deve estar dentro dos limites da matriz. Em outras palavras, ele deve ser grande o suficiente para reter os elementos trocados sem causar nenhum erro fora de limite.
2. A área de trabalho pode ser sobreposta a uma das duas matrizes classificadas; no entanto, ele deve garantir que nenhum dos elementos não imersos seja substituído.

Com esse algoritmo de fusão definido, é fácil imaginar uma solução, que pode classificar metade da matriz; A próxima pergunta é: como lidar com o restante da peça não classificada armazenada na área de trabalho, como mostrado abaixo:

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

Uma idéia intuitiva é classificar recursivamente outra metade da área de trabalho, portanto, existem apenas 1/4 dos elementos ainda não classificados.

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

O ponto chave nesta fase é que devemos mesclar os elementos 1/4 classificados B com os elementos A classificados 1/2, mais cedo ou mais tarde.

A área de trabalho é deixada, que contém apenas 1/4 elementos, grande o suficiente para mesclar A e B? Infelizmente não é.

No entanto, a segunda restrição mencionada acima nos dá uma dica, de que podemos explorá-la organizando a área de trabalho para se sobrepor a qualquer sub-matriz, se pudermos garantir a sequência de mesclagem de que os elementos não imersos não serão substituídos.

Na verdade, em vez de classificar a segunda metade da área de trabalho, podemos classificar a primeira metade e colocar a área de trabalho entre as duas matrizes classificadas da seguinte forma:

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

Essa configuração organiza efetivamente a sobreposição da área de trabalho com o subconjunto A. Essa idéia é proposta em [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Combinação prática no local ''. Nordic Journal of Computing, 1996].

Portanto, a única coisa que resta é repetir o passo acima, o que reduz a área de trabalho de 1/2, 1/4, 1/8,… Quando a área de trabalho se torna pequena o suficiente (por exemplo, apenas dois elementos restantes), podemos alterne para uma classificação de inserção trivial para finalizar esse algoritmo.

Aqui está a implementação no ANSI C com base neste 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);
    }
}

Onde wmerge é definido anteriormente.

O código fonte completo pode ser encontrado aqui e a explicação detalhada pode ser encontrada aqui

A propósito, esta versão não é a classificação de mesclagem mais rápida, porque precisa de mais operações de troca. De acordo com o meu teste, é mais rápido que a versão padrão, que aloca espaços extras em cada recursão. Mas é mais lento que a versão otimizada, que dobra a matriz original com antecedência e a utiliza para mesclagem adicional.

Incluindo seu "grande resultado", este documento descreve algumas variantes da classificação de mesclagem no local (PDF):

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

Classificação no local com menos movimentos

Tomi A. Pasanen, Jyrki Katajainen

É mostrado que uma matriz de n elementos pode ser classificada usando O (1) espaço extra, O (n log n / log log n) se move e n log ₂ n + O (n log log n) comparações. Este é o primeiro algoritmo de classificação no local que requer o (n log n) move-se no pior caso, garantindo comparações de O (n log n), mas devido aos fatores constantes envolvidos, o algoritmo é predominantemente de interesse teórico.

Eu acho que isso é relevante também. Tenho uma cópia impressa por aí, passada por um colega, mas não a li. Parece cobrir a teoria básica, mas não estou familiarizado o suficiente com o tópico para julgar o quão abrangente:

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

Mesclagem estável ideal

Antonios Symvonis

Este artigo mostra como mesclar de maneira estável duas seqüências A e B dos tamanhos m e n, m ≤ n, respectivamente, com atribuições O (m + n), comparações O (mlog (n / m + 1)) e usando apenas uma constante quantidade de espaço adicional. Esse resultado corresponde a todos os limites inferiores conhecidos ...

Realmente não é fácil ou eficiente, e sugiro que você não faça isso a menos que realmente precise (e provavelmente não precisará, a menos que seja um dever de casa, pois os aplicativos de mesclagem no local são principalmente teóricos). Você não pode usar o quicksort? O Quicksort será mais rápido de qualquer maneira com algumas otimizações mais simples e sua memória extra é O (log N) .

Enfim, se você deve fazer isso, então você deve. Aqui está o que eu encontrei: um e dois . Não estou familiarizado com a classificação de mesclagem no local, mas parece que a idéia básica é usar rotações para facilitar a mesclagem de duas matrizes sem o uso de memória extra.

Observe que isso é mais lento mesmo que a classificação de mesclagem clássica que não está no local.

A etapa crítica é fazer com que a mesclagem seja implementada. Não é tão difícil quanto essas fontes descobrem, mas você perde algo quando tenta.

Observando uma etapa da mesclagem:

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

Sabemos que a ordenada seqüência é menor do que tudo o resto, que x é menor do que tudo o resto na A , e que y é menor do que tudo o resto em B . No caso em que x é menor ou igual a y , basta mover o ponteiro para o início de A em um. No caso em que y é menor que x , você deve embaralhar y além de A para classificar . Esse último passo é o que torna isso caro (exceto em casos degenerados).

Geralmente é mais barato (especialmente quando as matrizes contêm apenas palavras únicas por elemento, por exemplo, um ponteiro para uma sequência ou estrutura) para trocar algum espaço por tempo e ter uma matriz temporária separada que você alterna entre elas.

Apenas para referência, aqui está uma boa implementação de uma classificação de mesclagem no local estável . Complicado, mas não tão ruim.

Acabei implementando uma classificação de mesclagem no local estável e uma classificação rápida no local estável em Java. Observe que a complexidade é O (n (log n) ^ 2)

Um exemplo de fusão sem buffer em 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);
     }
}

Um exemplo de fusão adaptativa (otimizada).

Adiciona código de suporte e modificações para acelerar a mesclagem quando um buffer auxiliar de qualquer tamanho está disponível (ainda funciona sem memória adicional). Usa mesclagem para frente e para trás, rotação de anel, mesclagem e classificação de pequenas seqüências e mesclagem 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 resposta possui um exemplo de código , que implementa o algoritmo descrito no artigo Mesclagem prática no local de Bing-Chao Huang e Michael A. Langston. Devo admitir que não entendo os detalhes, mas a complexidade dada da etapa de mesclagem é O (n).

De uma perspectiva prática, há evidências de que implementações puras no local não estão apresentando um desempenho melhor nos cenários do mundo real. Por exemplo, o padrão C ++ define std :: inplace_merge , que é o nome que implica uma operação de mesclagem no local.

Supondo que as bibliotecas C ++ sejam tipicamente muito bem otimizadas, é interessante ver como elas são implementadas:

1) libstdc ++ (parte da base de códigos do GCC): std :: inplace_merge

A implementação delega para __inplace_merge , que evita o problema ao tentar alocar um buffer temporário:

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

Caso contrário, ele retornará a uma implementação ( __merge_without_buffer ), que não requer memória extra, mas não é mais executada no tempo O (n).

2) libc ++ (parte da base de códigos Clang): std :: inplace_merge

Parece semelhante. Ele delega para uma função , que também tenta alocar um buffer . Dependendo se ele possui elementos suficientes, ele escolherá a implementação. A função de fallback de memória constante é chamada __buffered_inplace_merge .

Talvez até o fallback ainda esteja no tempo O (n), mas o ponto é que eles não usam a implementação se houver memória temporária disponível.

Observe que o padrão C ++ oferece explicitamente às implementações a liberdade de escolher essa abordagem, diminuindo a complexidade necessária de O (n) para O (N log N):

Complexidade: Comparações exatamente N-1 se houver memória adicional suficiente disponível. Se a memória for insuficiente, comparações O (N log N).

Obviamente, isso não pode ser tomado como prova de que o espaço constante no local se mescla no tempo O (n) nunca deve ser usado. Por outro lado, se fosse mais rápido, as bibliotecas C ++ otimizadas provavelmente mudariam para esse tipo de implementação.

Esta é a minha versão 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--;
    }
  }
}

Há uma implementação relativamente simples da classificação de mesclagem no local usando a técnica original do Kronrod, mas com uma implementação mais simples. Um exemplo pictórico que ilustra essa técnica pode ser encontrado aqui: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

Há também links para análises teóricas mais detalhadas do mesmo autor associado a este link.

Eu apenas tentei colocar o algoritmo de mesclagem no lugar para classificar no JAVA usando o algoritmo de classificação de inserção, seguindo as etapas a seguir.
1) Duas matrizes ordenadas estão disponíveis.
2) Compare os primeiros valores de cada matriz; e coloque o menor valor na primeira matriz.
3) Coloque o valor maior na segunda matriz usando a classificação por inserção (percorra da esquerda para a direita).
4) Compare novamente o segundo valor da primeira matriz e o primeiro valor da segunda matriz e faça o mesmo. Mas quando a troca acontece, há alguma pista para ignorar a comparação dos itens adicionais, mas é necessário apenas a troca.

Eu fiz alguma otimização aqui; para manter comparações menores na classificação de inserção.
A única desvantagem que encontrei com essas soluções é que ele precisa de uma troca maior de elementos da matriz na segunda matriz.

por exemplo)

Primeira___Array: 3, 7, 8, 9

Segunda matriz: 1, 2, 4, 5

Então 7, 8, 9 faz com que a segunda matriz troque (mova para a esquerda por um) todos os seus elementos um a cada vez para se colocar no último.

Portanto, a suposição aqui é trocar itens é insignificante comparar com a comparação de dois itens.

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