merge sort example c/c++ - 2

Following code fragment is another merge sort example written in 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.

#include <stdio.h>

#define LEN 9

void merge_sort(int num[],int start, int end); 

void merge(int num[], int start, int mid, int end);

void tracer(int num[],int len);

int main(void){

     

    int testArr[LEN] = {485,241,454,325,452,685,498,890,281};

    merge_sort(testArr, 0, LEN-1);

}

void merge_sort(int num[],int start, int end){

    int median = (start + end)/2; 

    if(start < end){ 

        merge_sort(num, start, median); 

        merge_sort(num, median+1, end); 

        merge(num, start, median, end); 

    }

}

void merge(int num[], int start, int median, int end){

    int i,j,k,m,n;

    int tempArr[LEN]; 

    i = start; 

    j = median+1; 

    k = start; 

    while (i <= median && j <= end){

        tempArr[k++] = (num[i] > num [j]) ? num [j++] : num [i++];

    }

     

    m = (i > median) ? j : i; 

    n = (i > median) ? end : median; 

    for (; m<=n; m++){ 

        tempArr[k++] = num[m];

    }

    for (m=start; m<=end; m++){

        num[m] = tempArr[m]; 

    }

    printf("Merging: %d ~ %d & %d ~ %d\n",start,median,median+1,end);

    tracer(num,LEN);

}

void tracer(int num[],int len){

    int i;

    for(i=0;i<len;i++){

        printf("%d\t",num[i]);

    }

    printf("\n\n");

}

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);

}