[알고리즘/c] 합병정렬

n개의 원소를 비내림차순(오름차순)으로 정렬

#include <stdio.h>
//합병정렬
 
void main(){
	int S[] = {27, 10, 12, 20, 25, 13, 15, 22};
	printf("정렬 전\n");
	for(int i=0; i<sizeof(S)/sizeof(int); i++){
		printf("%d ", S[i]);
	}
	mergeSort(S, 0, 7);
	printf("\n정렬 후\n");
	for(int i=0; i<sizeof(S)/sizeof(int); i++){
		printf("%d ", S[i]);
	}
}

void mergeSort(int S[], int left, int right){
	int mid;
	
	//분할이 아직 되지 않았을 경우 
	if(left<right){
		mid=(left+right)/2;
		mergeSort(S, left, mid);
		mergeSort(S, mid+1, right);
		merge(S, left, mid, right); //분할된 블록 병합 
	}
}

void merge(int S[], int left, int mid, int right){
	int i, j, k, m;
	i=left;
	j=mid+1;
	k=left; //결과 배열의 인덱스
	int U[8]; //합병에 필요한 임시배열
	
	while(i<=mid && j<=right){
		if(S[i]<S[j]){
			U[k]=S[i];
			i++;
		}else{
			U[k]=S[j];
			j++;
		}
		k++;
	}
	
	if(i>mid){//left블록이 모두 처리된 경우 
		for(m=j; m<=right; m++){
			U[k]=S[m];
			k++;
		}
	}else{//right블록이 모두 처리된 경우 
		for(m=i; m<=mid; m++){
			U[k]=S[m];
			k++;
		}
	}
	for(m=left; m<=right; m++){
		S[m]=U[m];
	}
}  

 

<실행화면>