병합 정렬(merge sort)

1. 원리

1. 먼저 데이터를 분할한다. (크기가 1인 리스트들이 남을 때까지) //mergesort
2. 합치면서 정렬을 같이한다. //merge

 

int main(){
	int data[8]={...};
	...
}

void mergesort(int data[], int p, int r){//p는 시작 인덱스, r은 마지막 인덱스
	int q;
	if(p<r){
    	q=(p+r)/2; //중간 인덱스 
        mergesort(data,p,q);  //재귀적으로 절반으로 쪼개나가기
        mergesort(data,q+1,r); 
        merge(data,p,q,r); //정렬하며 병합
     }
}

void merge(int data[], int p, int q, int r){
	int i=p, j=q+1, k=p;
    int temp[8]; // 정렬한 거 넣을 새 배열
    while(i<=q && j<=r){//오른쪽 배열이나 왼쪽 배열 중 하나라도 끝까지 접근했다면 반복문 탈출
    	if(data[i] <= data[j]) //오른쪽에 있는 배열의 값이 더 크거나 같다면
        	tmp[k++] = data[i++]; //새 배열에 왼쪽 배열 담기(후위 증가: k번째 인덱스에 값 담고 k값 1 증가)
        else tmp[k++] = data[j++]; //왼쪽 배열의 값이 더 크다면 새 배열에 오른쪽 배열 담기
    }
    while(i<=q) tmp[k++] = data[i++]; //아직 남아있는 왼쪽 배열 새 배열에 담기
    while(j<=r) tmp[k++] = data[j++]; //아직 남아있는 오른쪽 배열 새 배열에 담기
    for(int a = p; a<=r; a++) data[a] = tmp[a]; //원래 배열을 정렬된 새 배열로 덮어쓰기
}

과정 1

 

과정 2

 

 

과정 3