8-4) 정렬 - 합병 정렬

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

합병 정렬 (Merge sort)

 

합병 정렬은 요소가 하나만 남을 때가지 리스트를 쪼개고, 다시 합치는 과정에서 대소를 비교하여 정렬하는 방법이다. 

 

 

비교해야할 요소가 n이 있으면 그 중 반을 비교하면 되기 때문에 합병 정렬의 평균적인 시간 복잡도는 O(n logn)이다. 합병 정렬은 리스트를 쪼개어서 다른 공간에 저장한 뒤에 다시 merge 하므로 out-of-place 정렬이며, 중복된 숫자가 정렬 이전에 놓여있던 순서를 유지한 상태로 정렬되는 안정 정렬이다. 

 

합병 정렬 코드 구현

 

합병 정렬에서는 배열의 요소를 직접 건드리는 것이 아닌 배열의 index를 다룬다.

int[] array, temp;	// temp배열: array의 임시 복사본
public mergeSort(int[] array) {
	this.array = array;
	// 빈 배열을 만들어 데이터가 정렬되면 이를 저장
	temp = new int[array.length];
	split(0, array.length - 1);
}
// 리스트가 1개 남을 때까지 나눕니다.
private void split(int low, int high) {
	if (low == high) return;	// 배열 요소 1개이면 할 것 없음
	int mid = (high + low) / 2;
	split (low, mid)
	split (mid + 1, high)
	merge (low, mid, high)
}
// 대소 비교 후 순서에 맞게 열거합니다.
public void merge(int low, int mid, int high) {
	int i=low, j=mid+1, tempposn = low;	// 임시 인덱스 포인터
	// 나눈 리스트의 대소 비교와 정렬
	while (i <= mid && j <= high) {
		if (array [i] <= array [j])	// i요소가 j요소보다 작거나 같으면 임시 배열에 저장
			temp[tempposn++] = array[i++];
		else
			temp[tempposn++] = array[j++];
	}
	// // i가 mid로 가고 j가 high로 갈 때까지 반복
	while (i <= mid) {
    	temp[tempposn++] = array[i++];
	}
    while (j <= high) {
    	temp[tempposn++] = array[j++];
	}
    // 원래 배열에 다시 복사
	for (tempposn = low; tempposn <= high; tempposn++)
		array[tempposn] = temp[tempposn];
}