langc_algo_mergesort.c

#include <stdio.h>

#define MAX 50

int a[] = { 99, 11, 29, 44, 17, 55, 63, 05, 22, 42, 15, 12 ,21 };
int b[MAX];


int merge_merging(int src[], int dst[], int start, int mid, int end)
{
	int i,j,k;

//  printf("merging start=%02d mid=%02d end=%02d\n",start,mid,end);	
	
    i = start, j = mid;
    
    // While there are elements in the left or right runs...
    for (k = start; k < end; k++) {
 
        // If left run head exists and is <= existing right run head.
        if (i < mid && (j >= end || src[i] <= src[j])) {
            dst[k] = src[i];
            i++;
        } else {
            dst[k] = src[j];
            j++;    
        }
        
    } 
    
    return 0;
}




void merge_split(int tmp[],int src[], int start, int end) {
   int mid;
   
   if(end - start < 2)  // if run size == 1
        return;   
   mid = (start + end) / 2;    

 // printf(" split start=%02d mid=%02d end=%02d\n",start,mid,end);

   merge_split(src,tmp, start, mid);
   merge_split(src,tmp, mid, end);
   merge_merging(tmp,src,start,mid,end);
}

int merge_sort(int src[], int tmp[], int lens )
{
	int i;
	
	for(i=0;i<lens;i++)
		tmp[i] = src[i];
	
	merge_split(tmp,src,0,lens);
	
	return 0;
}



int main() { 
   int i;
   int lens;
   
   lens = sizeof(a)/sizeof(int);

   printf("List before sorting\n");
   
   for(i = 0; i < lens; i++)
      printf("%d ", a[i]);
      
   printf("\n");
   
 //  sort(0, lens);
	merge_sort(a,b,lens);

   printf("\nList after sorting\n");
   
   for(i = 0; i < lens; i++)
      printf("%d ", a[i]);
   
   printf("\n");
   
//   for(i = 0; i < lens; i++)
//      printf("%d ", b[i]);      
      
      
}