Wednesday, May 11, 2011

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