merge sort example c/c++

Following code fragment is a merge sort example written in c/c++ language. Merge sort algorithm is very similar to quick sort algorithm. Both partition the input data into two parts and recursively apply sort algorithm on them.

void MergeSort(int *naData, int nLen)

{

     int i = 0, nFHIdx = 0, nSHIdx = 0;    

     int nHalf = nLen / 2;              

     int *naFirstHalf, *naSecondHalf;

     if(nLen == 1)

          return;

  

     naFirstHalf = (int *)malloc(sizeof(int) * nHalf);

     naSecondHalf = (int *)malloc(sizeof(int) * nLen-nHalf);

    

     memcpy(naFirstHalf, naData, sizeof(int) * nHalf);

     memcpy(naSecondHalf, naData+nHalf, sizeof(int) * nLen-nHalf);

  

     MergeSort(naFirstHalf, nHalf);

     MergeSort(naSecondHalf, nLen-nHalf);

     while(nFHIdx < nHalf || nSHIdx < nLen-nHalf)      

     {

          if(nFHIdx == nHalf)

          {

                naData[i++] = naSecondHalf[nSHIdx++];

          }else if(nSHIdx == nLen-nHalf)

          {

               naData[i++] = naFirstHalf[nFHIdx++];

          }else if(naFirstHalf[nFHIdx] >= naSecondHalf[nSHIdx])

          {

               naData[i++] = naSecondHalf[nSHIdx++];

          }else

          {

               naData[i++] = naFirstHalf[nFHIdx++];

          }

     }

 

     free(naFirstHalf);

     free(naSecondHalf);

}