[알고리즘] 정렬 알고리즘 - 합병 정렬 Merge Sort

 

합병 정렬 (Merge Sort) 알고리즘 :

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘

 

int[] merge = {8, 1, 4, 2, 7, 6, 3, 5}

1. 배열을 반으로 나눈다

2. 앞부분을 합병정렬로 정렬한다

3. 뒷부분을 합병정렬로 정렬한다

배열 merge의 합병 정렬 과정

 

4. 앞부분과 뒷부분을 병합한다

   4-1. 앞부분을 배열 buff에 복사

   4-2. 배열 buff와 뒷부분을 배열 a에 병합

   4-3. 배열 buff의 나머지 요소를 배열 a에 복사

배열 merge의 앞부분과 뒷부분 병합 과정

 

 

메서드 mergeSort() : 배열 a의 크기 n과 같은 크기의 배열 buff를 선언하고, mergetSort()를 실행 후 정렬이 끝나면 배열 buff를 해제

매개변수 : int[] a, int n

 

메서드 mergeSort() : 배열 a의 index left 부터 right 까지 요소를 합병 정렬

매개변수 : int[] a, int left, int right

 

- 합병 정렬 : 

static int[] buff;

void mergeSort(int[] a, int n) {
	buff = new int[n];
	mergeSort(a, 0, n-1);
	buff = null;
}

void mergeSort(int[] a, int left, int right) {
	if(left < right) {
		int i;
		int center = (left + right) /2;
		int p = 0;
		int j = 0;
		int k = left;
			
		mergeSort(a, left, center);
		mergeSort(a, center + 1, right);
		
		for(i = left; i <= center; i++)
			buff[p++] = a[i];
            
		while(i <= right && j < p)
			a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
				
		while(j < p)
			a[k++] = buff[j++];
	}
}

 

 

 

 

합병 정렬 Merge Sort :

최선 = O(NlogN), 평균 = O(NlogN), 최악 = O(NlogN)

안정한 정렬