[C++] 병합정렬

병합정렬에 대한 설명을 위한 포스트가 아닌 개인적으로 코드를 저장하기 위해 작성된 포스트 입니다
개념 공부를 위해서는 다른사람 블로그를 참고 바랍니다.

+ 2024.12.20 수정
기존 코드에서 입력받은 객체에서 지정된 operator에 대해서만 정렬이 가능하다.

하지만 객체 내에 다양한 값에 대해서 특정 상황에 맞게 다르게 정렬하고 싶다면 같은 코드를 여러번 작성해야 하는데 이게 귀찮아서 비교함수를 넣는 방법과 비교함수를 따로 안넣으면 operator<에 의해 비교하도록 만들었다.

template<typename T, typename Compare>
void merge_sort(int left, int right, T *arr, Compare comp) {
	if (left >= right) return;

	int mid = (left + right) >> 1;
	merge_sort(left, mid, arr, comp);
	merge_sort(mid + 1, right, arr, comp);

	int i = left;
	int j = mid + 1;
	int size = right - left + 1;
	T* temp = new T[size];
	int k = 0;

	while (i <= mid && j <= right) {
		if (comp(arr[i], arr[j])) temp[k++] = arr[i++];
		else temp[k++] = arr[j++];
	}

	while (i <= mid) temp[k++] = arr[i++];
	while (j <= right) temp[k++] = arr[j++];

	for (int t = 0; t < size; ++t) {
		arr[left + t] = temp[t];
	}

	delete[] temp;
}

// Compare 인자를 받지 않는 오버로드
// 여기서 기본적으로 a < b를 비교하는 람다를 사용하여 기본 정렬 기준 제공
template<typename T>
void merge_sort(int left, int right, T *arr) {
	merge_sort(left, right, arr, [](const T &a, const T &b) {
		return a < b;
	});
}