[정렬 알고리즘, C#] 병합 정렬(Merge Sort)

■ 병합 정렬(Merge Sort)

[병합 정렬 원리]

병합 정렬은 배열을 계속 쪼개고(Divide), 나눠진 배열들을 병합(Conquer)하면서 정렬하는 분할 정복(Divide and Conquer) 알고리즘이다.

• 퀵 정렬이 피벗(Pivot)을 기준으로 배열을 좌우로 분할했다면, 병합 정렬은 배열의 가운데를 기준으로 반씩 나눈다.
• 배열의 길이가 1이 될 때까지 재귀적으로 분해하고, 그 후 병합하면서 정렬한다.

 

■ 병합 정렬 구현(C#)

1. 배열 분해

// 병합 정렬
public static void MergeSort(T[] arr, int left, int right)
{
	if (left >= right) return;
	
	var mid = (left + right) / 2;
	
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
	
	Merge(arr, left, mid, right);
}

먼저 배열의 중간 지점(mid)을 계산한 뒤, 이를 기준으로 배열을 왼쪽과 오른쪽 두 부분으로 재귀적으로 분해한다.

→ 이 과정은 배열의 길이가 1이 될 때까지 반복된다.

• 예를 들어 left = 0, right = 1인 상태라면, 배열에 존재하는 원소는 2개이다.
  • mid = 0
  • MeargeSort(arr, 0, 0)과 MeargeSort(arr, 1, 1)이 호출된다.

이후, 배열의 길이가 1이하가 되면, if (left >= right) 조건에 의해 더 이상 분해되지 않고, 재귀 호출의 이전 스택으로 되돌아가면서 저장된 left, mid, right 값을 기준으로 병합이 진행된다.

 

2. 배열 병합

private static void Merge(T[] arr, int left, int mid, int right)
{
    int leftIndex = left;
    int rightIndex = mid + 1;

    T[] tempArr = new T[right - left + 1];
    int k = 0;

    while (leftIndex <= mid && rightIndex <= right)
    {
        if (arr[leftIndex].CompareTo(arr[rightIndex]) <= 0)
        {
            tempArr[k++] = arr[leftIndex++];
        }
        else
        {
            tempArr[k++] = arr[rightIndex++];
        }
    }

    // 남은 배열 복사
    while (leftIndex <= mid) tempArr[k++] = arr[leftIndex++];
    while (rightIndex <= right) tempArr[k++] = arr[rightIndex++];

    // left ~ right 구간 정렬 완료 후, 원래 배열에 복사
    var j = 0;
    for (var i = left; i <= right; ++i)
    {
        arr[i] = tempArr[j++];
    }
}

left ~ mid 구간은 좌측 배열, mid + 1 ~ right 구간은 우측 배열이 된다.

각 배열의 원소를 가리키는 포인터(leftIndex, rightIndex)를 비교하면서, 더 작은 값을 먼저 임시 배열(tempArr)에 저장하는 방식으로 정렬을 수행한다.

• 이때, 넘어온 두 배열은 이미 **“정렬된 상태”**이므로, 어느 한쪽의 배열이 먼저 끝났다면 남은 배열은 순서대로 복사해도 정렬이 유지된다.

마지막으로, 정렬된 tempArr의 값을 원본 배열의 left~right 구간에 덮어쓰면 병합 정렬이 완료된다.

 

■ 병합 정렬의 시간복잡도

병합 정렬의 시간복잡도를 계산해보자.계산해 보자. 병합 정렬은 분할 → 병합의 단계로 이루어지니, 각 단계의 시간복잡도를 먼저 계산해 보자.

 

1. 분할 단계

배열을 계속 반으로 나누게 되면, 한 번 나눌 때마다 배열 길이는 $n$ → $\frac{n}{2}$ → $\frac{n}{4}$ → $...$ → 1이 된다.

즉, 어떤 배열의 길이가 $n$이라면, 이 배열이 더 이상 분할되지 않을 때까지 나눠야 하는 횟수는 다음과 같다.

$$ \log_2 n $$

• 따라서 분할 단계의 깊이는 $\log n$이 된다.

 

2. 병합 단계

병합할 때는 각 단계마다 모든 원소를 한 번씩 순회하면서,

1. 두 배열을 비교 정렬하고,
2. 정렬된 결과를 임시 배열에 저장한 뒤,
3. 원본 배열의 해당 구간에 덮어쓴다.

이 작업은 재귀의 각 레벨마다 한 번씩 이루어지며, 각 레벨에서는 전체 배열 크기 $n$만큼의 작업이 수행된다.

 

3. 최종 시간복잡도

각 단계가 $O(n)$의 연산을 하고, 이런 단계가 $\log n$번 일어나므로 :

$$ T(n) = O(n \log n) $$

• 그래서 병합 정렬은 입력 배열의 정렬 상태와 관계없이 항상 일정한 성능을 보장한다.