MergeSort(병합정렬)란?

• 분할 정복 알고리즘(Divide and Conquer)을 활용한 정렬이다.

  1) 배열을 계속 반으로 나누면서(좌우로) --->최소 단위(1개의 원소)까지 나누고 (분할)
  2) 최소 단위부터 좌우를 합치면서 정렬해나가는 방식 (병합 및 정렬)

#include <iostream>

void Merge(int arr[], int left, int mid, int right, int temp[])
{
	int i = left, j = mid + 1, k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] > arr[j])
		{
			temp[k] = arr[j];
			j++;
		}
		else
		{
			temp[k] = arr[i];
			i++;
		}
		k++;
	}

	while (i <= mid)
	{
		temp[k] = arr[i];
		i++;
		k++;
	}
	while (j <= right)
	{
		temp[k] = arr[j];
		j++;
		k++;
	}
	
	for (int i = left; i <= right; i++)
		arr[i] = temp[i];
}


void MergeSort(int arr[], int left, int right, int temp[])
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	MergeSort(arr, left, mid, temp); // 좌측 병합정렬
	MergeSort(arr, mid + 1, right, temp); // 우측 병합 정렬
	Merge(arr, left, mid, right, temp); // mid 기준 좌우 병합
}