0
I already know that it uses recursion and that it orders the vectors until they are ordered, but it is exactly in this part that it generates my doubts. How do I know when he will call the Merge method? When will he come out of the first merge and enter the second? Why does the merge only split the initial vector number with the end? When the while will be called?
#include <stdio.h>
#include <stdlib.h>
void mergeSort( int *vetorDesorndeado, int posicaoInicio, int posicaoFim )
{
int i,j,k,metadeTamanho,*vetorTemp;
if ( posicaoInicio == posicaoFim ) return;
// ordenacao recursiva das duas metades
metadeTamanho = ( posicaoInicio+posicaoFim )/2;
mergeSort( vetorDesorndeado, posicaoInicio, metadeTamanho);
mergeSort( vetorDesorndeado, metadeTamanho+1,posicaoFim );
// intercalacao no vetor temporario t
i = posicaoInicio;
j = metadeTamanho+1;
k = 0;
vetorTemp = (int *) malloc(sizeof(int) * (posicaoFim-posicaoInicio+1));
printf( " VALOR DE I : %d , VALOR DE J : %d , VALOR DE K : %d, VALOR DE FIM : %d \n ", i, j, k, posicaoFim);
while( i < metadeTamanho+1 || j < posicaoFim+1 )
{
if ( i == metadeTamanho+1 )
{ // i passou do final da primeira metade, pegar v[j]
vetorTemp[k] = vetorDesorndeado[j];
j++;
k++;
}
else
{
if (j==posicaoFim+1)
{
// j passou do final da segunda metade, pegar v[i]
vetorTemp[k] = vetorDesorndeado[i];
i++;
k++;
}
else
{
if (vetorDesorndeado[i] < vetorDesorndeado[j])
{
vetorTemp[k] = vetorDesorndeado[i];
i++;
k++;
}
else
{
vetorTemp[k] = vetorDesorndeado[j];
j++;
k++;
}
}
}
}
printf("\n");
// copia vetor intercalado para o vetor original
for( i = posicaoInicio; i <= posicaoFim; i++ )
{
vetorDesorndeado[i] = vetorTemp[i-posicaoInicio];
}
free(vetorTemp);
}
int main(){
int tamanho;
printf(" Qual o tamanho do vetor : ");
scanf("%d",&tamanho);
int vetor[tamanho];
for(int i = 0; i <= tamanho-1; i++){
printf(" Digite o %d numero ", i+1);
scanf("%d", &vetor[i]);
}
mergeSort(vetor,0,tamanho-1);
for(int i = 0; i < tamanho; i++){
printf(" %d ", vetor[i]);
}
return 0;
}
Have you looked at any other questions here from Sopt? I’m sure I’ve already mentioned how it works on a matter of computational complexity myself, maybe I have some direct question about it
– Jefferson Quesado
Here I mention how it works: https://answall.com/a/237026/64969 take two ordered lists and "create" a third ordered list
– Jefferson Quesado