병합 정렬(Merge Sort)

Merge_Sort.cc

#include<iostream>
#include<algorithm>
#define SIZE 1000
using namespace std;

void Merge(int arr[], int l, int r)
{
	int temp[SIZE];
	int mid = (l + r) / 2;
	int i = l;
	int j = mid + 1;
	int k = 0;

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

	//남은 수 temp로 옮기기
	while (i <= mid)
		temp[k++] = arr[i++];
	while (j <= r)
		temp[k++] = arr[j++];

	//원래 배열(arr)로 옮기기
	i = l;
	k = 0;
	while (i <= r)
		arr[i++] = temp[k++];
	
}

//Mergesort arr의 l~r 까지 mergesort
void Mergesort(int arr[], int l, int r)
{
	if (l == r)
		return;
	int mid = (l + r) / 2;
	Mergesort(arr, l, mid);
	Mergesort(arr, mid + 1, r);
	Merge(arr, l, r);
}

int main()
{
	int n;
	int arr[SIZE];

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	Mergesort(arr, 0, n - 1);

	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	cout << endl;

	return 0;
}