[자료구조] Merge Sort (합병 정렬)

<파이썬 알고리즘 인터뷰>  p.482, 책만, 2020

개념

분할정복 알고리즘 기법을 사용해서 배열을 작게 나누어 분할한뒤 다시 합치는 (병합, 합병하는) 방식의 정렬

퀵 정렬보다는 성능이 떨어짐
데이터 크기만한 메모리가 필요함
안정적 정렬

n-way 합병 정렬

1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할

2.부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성
  마지막 남은 부분리스트가 정렬된 리스트

2-way 합병 정렬

1. 리스트의 길이가 1 이하이면 이미 정렬된 상태

2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔

3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬

4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병 (이때 정렬 결과는 임시배열에 저장)

5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

시간복잡도

(Worst Case = Best Case = Average Case)

O(n log n)

 

예제 코드

void mergeSort(int list[], int start, int mid, int end)
{
  int i, j, k;
  int temp[11];

  i = start;
  j = mid + 1;
  k = start;

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

  if (i > mid)
  {
    for (int l = j; l <= end; l++)
    {
      temp[k++] = list[l];
    }
  }
  else
  {
    for (int l = i; l <= mid; l++)
    {
      temp[k++] = list[l];
    }
  }

  for (int l = start; l <= end; l++)
  {
    list[l] = temp[l];
  }
}

void merge(int list[], int start, int end)
{
  int mid;
  if (start < end)
  {
    mid = (start + end) / 2;
    merge(list, start, mid);
    merge(list, mid + 1, end);
    mergeSort(list, start, mid, end);
  }
}