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