Merge Sort
분할 정복 (divdie and conquer) 방법을 통해 주어진 배열을 정렬한다.
분할 정복 : 문제를 작은 문제로 분할해서 해결한 다음, 합쳐서 결과를 내는 방법.
MergeSort는 먼저 배열의 원소가 최소가 될 때 까지 분할하고 합치면서 정렬한다.
정렬 과정
- 배열의 원소의 갯수가 최소가 될떄까지 분할 한다.
- 두 배열의 인덱스를 비교하면서 작은 값부터 새로운 배열에 넣는다.
void mergeSort(int[] array, int start, int end)
{
if (start >= end) return;
int mid = (start + end) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
int[] tmp = new int[array.Length];
int i = start, j = mid + 1, k = start;
while (i <= mid && j <= end)
{
tmp[k++] = array[i] < array[j] ? array[i++] : array[j++];
}
// 두 배열을 비교하면서 작은 값부터 새로운 배열에 넣어준다.
while (i <= mid) tmp[k++] = array[i++];
while (j <= end) tmp[k++] = array[j++];
// 두 배열중 남은 배열을 처리한다.
while (start <= end)
{
array[start] = tmp[start++];
}
// 임시 배열을 원본배열로 옮긴다.
}