merge sort é duplicatiing array entries - java, arrays, algoritmo, classificação

Eu estava tentando implementar em Java o tipo de mesclagemalgoritmo de acordo com a Introdução aos algoritmos de Cormen. O problema com o meu código (abaixo) é que a matriz principal está duplicando algumas de suas entradas durante a etapa de mesclagem.

Alguém é capaz de entender o que estou fazendo de errado?

Obrigado!

  static void merge(int a[], int p, int q, int r)
{
int n1 = q - p;
int n2 = (r - q);
int [] left = new int[n1 + 1];
int [] right = new int[n2 + 1];
int pp = p;
int qq = q;
for(int i = 0; i < n1; i++)
{
left[i] = a[++pp];
}
for(int i = 0; i < n2; i++)
{
right[i] = a[++qq];
}
left[left.length-1] = Integer.MAX_VALUE;
right[right.length-1] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for(int k = p; k < r; k++)
{
if(left[i] <= right[j])
{
a[k] = left[i];
i++;
}
else
{
a[k] = right[j];
j++;
}
}
}

static int [] mergeSort(int a[], int p, int r)
{
if(p < r)
{
int q = (p + r)/2;
mergeSort(a, 1, q);
mergeSort(a, q + 1, r);
merge(a, p, q, r);
}
return a;
}

Respostas:

1 para resposta № 1

Parte da questão aqui é o exemplo doaparentemente, o livro usa um intervalo de índice de 1 a comprimento. Será mais simples se você alterar o intervalo do índice de 0 para comprimento-1, o que eu assumo no restante da minha resposta.

Use o pós-incremento enquanto copia para a esquerda [] e para a direita [] conforme respondido por laune (desde o intervalo de índice de 0 a comprimento-1).

                left[i] = a[pp++];
...
right[i] = a[qq++];

O principal problema é que a função de mesclagem não está verificando se chegou ao final da execução esquerda ou direita durante uma mesclagem. Isso pode ser corrigido alterando o interno se:

                if (i < n1 && (j >= n2 || left[i] <= right[j]))

As chamadas recursivas para mesclar a classificação devem ser:

                mergeSort(a, p, q);
mergeSort(a, q, r);

Não mostrado, mas a chamada inicial para mergeSort deve ser:

                mergeSort(a, 0, a.length);

Não há necessidade de alocar o elemento extra à esquerda e à direita (já que o intervalo do índice é de 0 a comprimento 1).

            int [] left = new int[n1];
int [] right = new int[n2];

---

1 para resposta № 2

Eu acho que isso está errado (assim como seu irmão no próximo loop):

left[i] = a[++pp];

Você deseja copiar começando com pp = p, portanto, não aumente antes de acessar o elemento da matriz:

left[i] = a[pp++];

---