Merge Sort 구현

C++를 이용하여 Merge Sort를 구현한 소스코드이다.

Merge를 할 때 원래는 마지막인지 체크를 하고 값을 넣는 과정이 있어야 하지만, 이렇게 하면 코드가 복잡해지기 때문에 합치려는 배열의 사이즈를 1씩 증가시켜서 마지막에 INT형 범위의 최댓값을 넣는 방법으로 구현하였다.

#include <iostream>

using namespace std;

#define INTMAX 2147483647

void mergeSort(int[], int, int);
void merge(int[], int, int, int);

int main(){
	int *arr, N;
	cin >> N;
	arr = new int[N];
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	mergeSort(arr, 0, N - 1);
	for (int i = 0; i < N; i++)
		cout << arr[i] << " ";
	return 0;
}

void mergeSort(int arr[], int s, int e){
	if (s >= e){
		return;
	}
	if (s + 1 == e){
		if (arr[s] > arr[e]){
			int tmp = arr[s];
			arr[s] = arr[e];
			arr[e] = tmp;
		}
	}
	else {
		int mid = (s + e) / 2;
		mergeSort(arr, s, mid);
		mergeSort(arr, mid + 1, e);
		merge(arr, s, mid, e);
	}
}

void merge(int arr[], int s, int mid, int e){
	int *t1 = new int[mid - s + 2];
	int *t2 = new int[e - mid + 1];
	for (int i = s; i <= mid; i++){
		t1[i - s] = arr[i];
	}
	t1[mid - s + 1] = INTMAX;
	for (int i = mid + 1; i <= e; i++){
		t2[i - mid - 1] = arr[i];
	}
	t2[e - mid] = INTMAX;
	int j = 0, k = 0;
	for (int i = s; i <= e; i++){
		if (t1[j] < t2[k]){
			arr[i] = t1[j++];
		}
		else {
			arr[i] = t2[k++];
		}
	}
	delete[] t1;
	delete[] t2;
}

메인함수 부분에서는 N개의 데이터를 입력 받아서 그 데이터를 MergeSort를 이용해서 정렬하고, 결과를 출력한다.