[알고리즘] 정렬4: merge sort

Merge Sort

bottom-up으로 하위 그룹의 정렬부터 상위 그룹 정렬로 올라가며 정렬한다.
머지 정렬은 bottom-up으로 정렬 그룹이 2개 이하일 때를 종료 조건으로 하고, 하위 그룹의 머지 정렬이 끝나면 상위 그룹에서 두 개의 그룹을 합치는 것으로 동작한다.
작은 그룹들이 밑에서부터 미리 정렬되어 있기 때문에 정렬된 그룹간의 정렬이 빠르다는 것을 이용한다. linear하게 비교하면서 merge만 하면 바로 정렬된 상위 그룹을 만들 수 있다.
재귀함수를 사용하여 구현한다.

ex)
5 1 9 3 4 6 2 : 반씩 나눈다.
5 1 9 || 3 4 6 2 : 반
5 | 1 9 || 3 4 | 6 2 : 반
5 | 1 9 || 3 4 | 2 6 : 두 개 이하가 되면 정렬하고 리턴함.
1 5 9 || 2 3 4 6 : 두 그룹을 정렬한다. 리턴한다.
1 2 3 4 5 6 9 : 두 그룹을 정렬한다. 리턴한다.
완료

void mergeSort(int arr[], int size) {
 if (size > 2) {
  // 왼쪽 반, 오른쪽 반을 나누어 반복.
  mergeSort(arr, size / 2);
  mergeSort(arr + size / 2, size - size / 2);

  // 왼쪽, 오른쪽 반이 각각 정렬된 상태임. merge한다.
  int leftCursor = 0;
  int rightCursor = size / 2;
  int buff[50];
  int buffCursor = 0;
  // 두 그룹을 각각 스캐닝하면서 순서대로 기록. (어느 한쪽이 끝날때까지)
  while (leftCursor < size / 2 && rightCursor < size) {
    if (arr[leftCursor] < arr[rightCursor]) {
    buff[buffCursor++] = arr[leftCursor++];
   } else {
     buff[buffCursor++] = arr[rightCursor++];
   }
  }
  // 남은 한 그룹의 데이터를 append 
  for (int i = leftCursor ; i < size / 2 ; i++)
    buff[buffCursor++] = arr[i];
  for (int j = rightCursor ; j < size ; j++) 
    buff[buffCursor++] = arr[j];
  memcpy(arr, buff, size * sizeof(int));
 }else { // 원소 개수가 2개 이하인 경우, 비교하여 정렬한다.
  if (arr[0] > arr[1])
    swap(arr[0], arr[1]);
 }
}