How does a Merge sort work exactly?

0

I already know that it uses recursion and that it orders the vectors until they are ordered, however, it is exactly in this part that generates my doubts. How do I know when it will call the Merge method? When will he leave the first merge and enter the second? What's the reason the merge is only dividing the number of the initial vector with the end? When will the while 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;
    }
    
asked by anonymous 19.11.2018 / 00:16

0 answers