[ALGORITHM] 19. 병합 정렬 구현하기

병합 정렬(Merge Sort)은 1945년 존 폰 노이만이 제안한 분할 정복(Divide and Conquer) 알고리즘의 일종으로,

정렬되지 않은 리스트를 반으로 나눈 후 각 부분을 재귀적으로 정렬하고,

정렬된 부분을 병합하여 전체 리스트를 정렬하는 방식을 취한다.

이 과정은 리스트의 길이가 1이 되거나 비어있을 때까지 반복되며, 안정적이면서 효율적인 정렬 방법으로 널리 사용된다.

 

template<typename T>
void merge(std::vector<T>& data, int left, int mid, int right) {

	int size = right - left + 1;

	std::vector<T> buff(size);

	int i = left, j = mid + 1, k = 0;

	while (i <= mid && j <= right) {

		if (data[i] <= data[j]) {

			buff[k++] = data[i++];
		
		} else {

			buff[k++] = data[j++];
		}
	}

	while (i <= mid) {

		buff[k++] = data[i++];
	}

	while (j <= right) {

		buff[k++] = data[j++];
	}

	for (int x = 0; x < size; x++) {

		data[left + x] = buff[x];
	}
}

template<typename T>
void merge_sort(std::vector<T>& data, int left, int right) {

	if (left < right) {

		int mid = left + (right - left) / 2;

		merge_sort(data, left, mid);
		merge_sort(data, mid + 1, right);
		merge(data, left, mid, right);
	}
}

 

 

특징

 

1. 안정 정렬(Stable Sort) : 동일한 키 값을 가진 원소의 상대적인 순서가 정렬 전후에 유지된다.

2. 외부 정렬에도 적용 가능 : 내부 정렬뿐만 아니라 외부 정렬에도 적용할 수 있는 유연한 알고리즘이다.

 

 

장점

 

1. 안정성 보장 : 동일한 값에 대해 상대적인 순서가 유지가 보장된다.

2. 외부 정렬에 유용 : 큰 데이터셋이나 외부 메모리에서의 정렬에 효율적으로 사용될 수 있다.

3. 파일 분할 및 병합에 유용 : 정렬된 파일을 합치거나 정렬된 상태에서 새로운 데이터를 추가하는 경우에도 효과적이다.

 

 

단점

 

1. 추가적인 메모리 사용 : 임시 배열이나 버퍼가 필요하므로 추가적인 메모리 사용이 필요하며,

이는 메모리 제약이 있는 상황에선 단점으로 작용한다.

2. 다른 알고리즘 대비 비교적 느릴 수 있음 : 퀵 정렬과 같은 일부 다른 정렬 알고리즘에 비해 상대적으로 느릴 수 있으며,

데이터셋이 작거나 이미 정렬된 경우에도 부가적인 비용이 발생할 수 있다.