苗火 Nicholas

[Data Structures]Merge sort

2019-5-22 萧 写技术

#include <stdio.h>
#include <stdlib.h>

void merge(int *dst, int *src, int left, int middle, int right)
{
	int i,j,k;

	k = left;
	i = left;
	j = middle+1;
	while( i<=middle && j<=right ){
		if(src[i] < src[j]){
			dst[k++] = src[i++];
		}else{
			dst[k++] = src[j++];
		}
	}

	if(j<=right){
		while(j<=right){
			dst[k++] = src[j++];
		}
	}else{
		while(i<=middle){
			dst[k++] = src[i++];
		}
	}
}

void mSort(int *dst, int *src, int left, int right)
{
	int i;
	if(left == right){
		dst[left] = src[right];
	}else{
		mSort(dst, src, left, (left+right)/2);
		mSort(dst, src, (left+right)/2+1, right);
		merge(src, dst, left, (left+right)/2, right);
		for(i=left; i<=right; i++){
			dst[i] = src[i];
		}
	}
}

void mergeSort(int *seq, int len)
{
	int dst[100];
	mSort(dst, seq, 0, len-1);
}
					
void main()
{
	int ancient[] = {49,38,65,97,76,13,27,49};
	int seq[] = {49,38,65,97,76,13,27,49};
	int n = sizeof(seq)/sizeof(int);
	int i;

	printf("Simple selection sort: \n");
	printf("Seq:\n");
	for (i=0; i<n; i++) {
		seq[i] = ancient[i];
		printf(" %2d", seq[i]);
	}	
	printf("\n");
	mergeSort(seq, n);
	for (i=0; i<n; i++) {
		printf(" %2d", seq[i]);
	}	
	printf("\n");

}

标签: Data Structures data_structures