합병정렬 / 병합정렬 (Merge Sort)

한유진·2021년 10월 23일

알고리즘

목록 보기

4/8

정의

문제를 분할하고, 분할한 문제를 정복하여 합치는 알고리즘 (분할 정복)

정렬 방법

주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할)
해당 부분리스트의 길이가 1이 아니라면 1번 과정 되풀이
인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복)

코드

재귀 (Top-Down 형식)

private static int[] sorted; //정렬하여 원소를 담을 임시 배열
private static void mergeSort(int[] a, int left, int right) {
	if(left == right) return; 
    //부분리스트가 1개의 원소만 갖는 경우 더이상 쪼갤 수 없음
    
    int mid = (left + right) / 2; //절반 위치
    
    mergeSort(a, left, mid); //절반 중 왼쪽 부분리스트
    mergeSort(a, mid + 1, right); //절반 중 오른쪽 부분리스트
    
    merge(a, left, mid, right); //병합
}
private static void merge(int[] a, int left, int mid, int right) {

	int l = left; //왼쪽 부분리스트 시작점
    int r = mid + 1; // 오른쪽 부분리스트 시작점
    int idx = left; //채워넣을 배열의 인덱스
    
    while(l <= mid && r <= right) {
    	//왼쪽 부분리스트 1번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우 왼쪽의 1번째 원소를 새 배열에 넣고 1과 idx를 1증가시킴
    	if(a[l] <= a[r]) {
        	sorted[idx++] = a[l++];
        }
        else {
        	sorted[idx++] = a[r++];
        }
   	}
    if(l > mid) {//왼쪽 부분리스트가 먼저 모두 다 채우졌을 경우 = 오른쪽 원소가 아직 남아있을 경우
    	while(r <= right) {
        	sorted[idx++] = a[r++];
        }
    }
    else {
    	while(l <= mid) {
        	sorted[idx++] = a[l++];
        }
    }
    for(int i = left; i <= right; i++) {
    	a[i] = sorted[i]; //새 배열을 기존의 배열에 복사하여 옮겨준다.
    }
}