How does a Merge Sort work exactly?

Asked

Viewed 166 times

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

  • Here I mention how it works: https://answall.com/a/237026/64969 take two ordered lists and "create" a third ordered list

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.