병합 정렬 소개

• 안정 정렬에 속하며, 분할-정복 알고리즘 중 하나
• 존 폰 노이만에 의해 개발됐다.

분할 정복 알고리즘?

병합 정렬은 분할 정복 알고리즘이다.
분할 정복 알고리즘이란 무엇일까.

분할 정복 알고리즘은 크게 분할, 정복, 결합 과정으로 나누어진다.

1. 분할
   문제를 해결하기 위해서 더 작은 규모의 문제로 쪼갬

2. 정복
   작게 나누어진 문제들을 개별적으로 해결

3. 결합
   해결된 개별의 문제들을 다시 합쳐서 원래의 문제를 해결하는 과정

병합 정렬의 단계별 과정

1. 분할
   배열을 절반으로 나누고, 길이가 1이 될 때 까지 반복한다.
   예를 들어서 38, 27, 43, 3, 9, 82, 10, 12] 길이 1이 될 때까지 다 나누면
   [38], [27], [43], [3], [9], [82], [10], [12]의 모습이 된다.

2. 정복 + 결합
   병합 정렬은 정복과 결합이 동시에 이루어진다.
   각 인접한 배열들끼리 요소에서 가장 작은 것부터 앞에 두며 병합한다.
   
   예시)
   1) [38], [27], [43], [3], [9], [82], [10], [12]
   2) [27, 38], [3, 43], [9, 82], [10, 12]
   3) [3, 27, 38, 43], [9, 10, 12, 82]
   4) [3, 9, 10, 12, 27, 38, 43, 82]
   결합이 완료되면 위와 같이 정렬된다.

병합 정렬의 구현

private void MergeSort(List<Ranking> list)
{
    if (list.Count <= 1)
        return;

    int mid = list.Count / 2;
    List<Ranking> left = new List<Ranking>(list.GetRange(0, mid));
    List<Ranking> right = new List<Ranking>(list.GetRange(mid, list.Count - mid));

    MergeSort(left);
    MergeSort(right);

    Merge(list, left, right);
}

• 현재 리스트를 절반으로 나누고 그 리스트를 매개변수로 재귀적인 호출을 반복한다.
• 만약 매개변수인 리스트의 길이가 1이하라면 즉시 반환한다.
• 반환이 시작되면 절반으로 나뉜 리스트들을 Merge메서드의 매개변수로 주어 병합한다.

private void Merge(List<Ranking> list, List<Ranking> left, List<Ranking> right)
{
    int i = 0, j = 0, k = 0;

    while (i < left.Count && j < right.Count)
    {
        if (left[i].Score >= right[j].Score)
        {
            list[k++] = left[i++];
        }
        else
        {
            list[k++] = right[j++];
        }
    }

    while (i < left.Count)
    {
        list[k++] = left[i++];
    }

    while (j < right.Count)
    {
        list[k++] = right[j++];
    }
}

• 병합을 저장할 리스트(list)와, 작게 나뉘어진 두 개의 리스트(left, right)를 매개변수로 받는다.
• left와 right의 맨 앞 요소를 비교해서 더 작거나 같은 요소를 list에 추가해준다.
  => list에 작은 순서대로 요소가 쌓인다.
• left 혹은 right에 요소가 남아있다면 순서대로 list에 추가해준다.

병합 정렬의 시간 복잡도

병합 정렬의 시간 복잡도는 항상 O(n log n)이다.
분할 단계가 (log n) 번 진행되고, 각 단계에서 병합 작업이 리스트의 길이에 비례하여 (O(n)) 시간이 소요된다.

두 요소를 곱하면 O(n log n)가 나온다.

그리고 모든 케이스에서 동일한 과정을 거치기 때문에 빠르거나 느려도 O(n log n)의 시간 복잡도를 가진다.

병합 정렬의 장단점

장점

• 예측 가능한 성능
  최선, 평균, 최악에서 모두 O(n log n)의 성능을 내어 성능 예측이 가능하다.

• 안정성
  동일한 요소를 정렬 시 순서가 유지된다.
  두 개의 연속 데이터에서 하나씩 비교하여 정렬할 때, 비교하는 요소가 동일한 값인 경우에 원래의 순서를 유지한 채로 정렬이 된다.

단점

• 추가 메모리 사용
  배열이나 리스트를 나눌 때 새로운 공간이 필요하기 때문에 추가로 메모리가 더 필요하다.
  메모리가 제한적인 상황에서는 사용 고려할 필요 있음.

• 재귀 호출 오버헤드
  재귀 호출로 인한 오버헤드가 배열, 리스트의 길이와 비례하여 자주 발생한다.

• 비교적 높은 상수 계수
  배열을 병합할 때 데이터 복사가 자주 일어나며, 배열들이 인접해있지 않을 수 있기 때문에 메모리 캐시 효율성이 떨어진다.
  이런 특징들과 위에 적은 단점들 때문에 상수 계수가 높아질 수 있다.

병합 정렬 최적화

병합 정렬은 이론 상 이상적인 정렬 알고리즘이지만, 실제로는 상수 계수가 높을 수 있다는 예측 불가능한 단점이 있다.
이를 해결하기 위한 최적화 방법이 있다. (우선 2개 정도만)

1. 삽입 정렬과의 하이브리드
   배열의 나눠지는 최소 길이를 정해놓고, 그 기준에 맞게 제일 작게 나눠진 배열은 삽입 정렬을 사용하는 것이다.
   이렇게 하면 단점에 적어놓은 상수 계수가 높아지는 것을 해소할 수 있다.

2. 상향식 병합 정렬
   재귀 호출을 사용하지 않는 병합 정렬인데, 아직 이해도가 낮아서 따로 포스팅할 예정이다.