병합정렬(Merge Sort) 분석과 소스 작성해 보기

이 알고리즘 역시 이해는 어렵지 않다.
트리구조로 파악 후 하위트리들을 작은수를 앞에 놓는 식으로 차례차례 상위로 이동하면서 병합하는 방식이다.
그런데 이해는 쉽게 되는데 선뜻 코드가 바로 짜여지지 않는다.
아무래도 트리구조로 탐색, 이동해야 되니 이동방식에 대한 고민이 만만찮고
배열 갯수가 2의 제곱으로 나누어지지 않는 부분에 대한 처리도 신경써야 되기 때문일 것이다.
여기저기 참고하고, 손질 좀 하고 시간 좀 걸려 짜 놓은 소스를 보니
참 길고 루프문도 많이 사용됨을 볼 수 있었다. 사용된 지역변수가 11개나 된다.

원래 각 트리 단계별로 보통 버퍼에 결과를 저장한 후 다시 원본배열로 이를 복사하는 방식을 사용하기도 하지만
이를 개선하는 방법도 있다.(이재규 알고리즘 서적 참조)
어차피 버퍼와 원본배열은 같은 크기이므로 서로 포인터만 바꾸어 다음번 루프에서는
원본이 버퍼가 되고 버퍼가 원본이 되게 처리가능하다. 물론 이 경우는 모든 정렬이 완료된 후
자리가 뒤바껴있으면 원본배열에 복사하는(되돌려 놓는) 과정이 필요할 것이다.

Merge Sort서 주의해야 될 점은 우선 사이즈가 다른 경우의 처리이다.
가령 트리레벨 4,4,4,3 의 경우 다음단계는 (4+4)와 (4+3)의 병합이다.
배열의 길이가 2의 제곱들이 아니면 끝 부분은 항상 딱 떨어지지 않게 된다.
이 경우에 두번째 비교부분은 항상 배열의 길이 내에서 유효하게 되는 코딩을 해야 된다.

다음으로 포인터를 교환해 오버헤드를 줄이는 방식을 취하는 경우(개선 버전) 신경써야 되는게
비교할 배열이 없는 경우이다.
예를 들어 트리레벨에서  4개, 4개, 2개인 경우 그 다음 과정은 (4개+4개)와 (2개) 과정이다.
(4개+4개)의 첫번째 부분은 노말하므로 역시 노말한 병합과정을 거치면 된다.
두번째 부분의 경우 비교할 필요가 없어  비교 루틴을 바로 탈출하면 되지만
이 때 비교할 필요 없는 해당 부분을 버퍼에 반드시 복사해줘야 된다.
포인터를 상호교환하는 방식이므로 이전 내용이 온전히 복사되어야 한다.
이 작업을 하지 않으면 처리하지 않는 부분에는 그 전단계의 배열형태가 남아있게 된다.
(글로 서술하니 좀 복잡해보이지만 디버그하면 그냥 보인다.)  이 부분을 잊고 누락하기 쉽다.

참고로 이재규 알고리즘 강의 역시 참고했는데 이 분 강의 매뉴얼 역시 이와 관련해 위 코드를 누락하고 있었다.
(기타 홀수인 경우도 문제가 있었다. 소스코드도 중복비교도 많고 해당 소스 부분은 썩 좋지 않은듯 하다.)

참고로 STL의 경우 Stable Sort를 병합정렬+삽입정렬(갯수가 32이하인 경우)로 구성하고 이를 재귀형태로 취한다.
tempbuf를 인수로 주고 이 버퍼길이이하일때까지 재귀를 통하여 잘게 쪼개고,,,
그 버퍼길이 이하이면 이제 병합하면서 정렬해나가는 방식이다.

아래소스는 재귀의 형태로 구성하지 않았다.
서적과 웹을 참고해서 잘못된 부분과 중복 비교 등 답답한 부분을 수정했다.




//------------------ 작성한 소스 ------------------




// 병합 정렬
// 불필요한 복사 줄이기 위해 원본 배열과 버퍼 간 포인터 교환(개선된 버전)
template <typename T> void __stdcall MergeSort(T *arr, int n)
{
 int i, j, k, size, left, right, leftlimit, rightlimit;
 T *buf, *tmp, *org;
 
 if(n<2) return;

 // 전달된 배열 크기만큼 버퍼 할당
 buf=(T*)malloc(sizeof(T)*n);
 if(!buf){
  MessageBoxW(NULL, L"버퍼 할당에 실패하였습니다.", L"MergeSort 에러", MB_TOPMOST|MB_ICONERROR);
  return;
 }

 // org에 원래 배열 주소 복사(아래서 정렬과정 거친 후 최후 결과 담긴 곳이 원본배열인지 판단하는 데 쓰임)
 org=arr;

 // size가 1, 2, 4, 8, 16,,, 이진 트리구조에서 하위->상위처럼 진행될 것이다.
 for(size=1 ; size<n ; size=(size<<1)){
  left=0;
  right=size;

  // size에 맞춰 개별적 비교
  do{ // 일단 무조건 한번은 통과하므로 do~while문 구성
   i=left;  // left 부분 첫 인덱스
   j=right; // right 부분 첫 인덱스
   k=left;  // merge 부분(버퍼) 첫 인덱스

   // 좌, 우측 한계치 설정
   leftlimit=left+size;
   if(right+size>n){ // 원본 배열 크기 초과한 경우 한계는 끝 부분
    rightlimit=n;
   } else {
    rightlimit=right+size;
   }

   // 값 비교 및 버퍼에 입력
   while(i<leftlimit && j<rightlimit){
    if(arr[i]>arr[j]){
     buf[k]=arr[j++];
    } else {
     buf[k]=arr[i++];
    }
    ++k;
   }
   if(i==leftlimit){ // 위에서 한쪽이 비워진 경우 나머지는 일괄적으로 채우면 됨
    while(j<rightlimit){
     buf[k++]=arr[j++];
    }
   } else {
    while(i<leftlimit){
     buf[k++]=arr[i++];
    }
   }

   // 다음 비교부분으로 이동
   left += (size<<1);
   right += (size<<1);

  } while(right<n);

  // 루프 탈출시 비교되지 않고 넘긴 부분 있는지 판단해서 복사
  // (right 부분이 존재하지 않아 비교할 필요가 없는 경우가 이에 해당)
  while(j<n) buf[k++]=arr[j++]; // j<n인 경우가 위의 경우

  // 불필요한 복사 줄이기 위해 원본 배열과 버퍼 간 포인터 교환
  tmp=arr; arr=buf; buf=tmp;
 }

 // 처음에 버퍼로 할당한 공간에 최종 결과가 담겨 있으면,,, 원본 배열에 복사해 줌
 if(org != arr){
  buf=arr;
  for(i=0 ; i<n ; i++) org[i]=buf[i];
 }
 
 free(buf);
}

// ------------- 구 버전 -------------//
// 병합 정렬
// 불필요한 복사 줄이기 위해 원본 배열과 버퍼 간 포인터 교환(개선된 버전)
template <typename T> void __stdcall MergeSortOld(T *arr, int n)
{
 int first, second, i, j, k, size, size2;
 T *buf, *tmp, *org;
 
 if(n<2) return;

 // 전달된 배열 크기만큼 버퍼 할당
 buf=(T*)malloc(sizeof(T)*n);
 if(!buf){
  MessageBoxW(NULL, L"버퍼 할당에 실패하였습니다.", L"MergeSort 에러", MB_TOPMOST|MB_ICONERROR);
  return;
 }

 // org에 원래 배열 주소 복사(아래서 정렬과정 거친 후 최후 결과 담긴 곳이 원본배열인지 판단하는 데 쓰임)
 org=arr;

 // size가 1, 2, 4, 8, 16,,, 이진 트리구조에서 하위->상위처럼 진행될 것이다.
 for(size=1 ; size<n ; size=(size<<1)){
  first=0;
  second=size;

  // size에 맞춰 개별적 비교
  do{ // 일단 무조건 한번은 통과하므로 do~while문 구성
   i=first; // 첫번째 비교부분 첫 인덱스
   j=second; // 두번째 비교부분 첫 인덱스
   k=first; // 병합할 버프의 첫 인덱스

   // size2 결정: 요소의 수가 2의 제곱이 아닌 경우 두번째 비교부분 사이즈 고려
   if(second+size>n){
    size2=n-second;
   } else {
    size2=size;
   }

   // 값 비교 및 버퍼에 입력
   while(i<first+size && j<second+size2){
    if(arr[i]>arr[j]){
     buf[k]=arr[j++];
    } else {
     buf[k]=arr[i++];
    }
    ++k;
   }
   if(i==first+size){ // 위에서 한쪽이 비워진 경우 나머지는 일괄적으로 채우면 됨
    while(j<second+size2){
     buf[k++]=arr[j++];
    }
   } else {
    while(i<first+size){
     buf[k++]=arr[i++];
    }
   }

   // 다음 비교부분으로 이동
   first += (size<<1);
   second += (size<<1);

  } while(second<n);

  // 루프 탈출시 비교되지 않고 넘긴 부분 있는지 판단해서 복사 필요
  // (second 비교부분이 존재하지 않아 비교할 필요가 없어 바로 루프 탈출한 경우)
  while(j<n) buf[k++]=arr[j++]; // j<n인 경우가 위의 경우에 해당.

  // 불필요한 복사 줄이기 위해 원본 배열과 버퍼 간 포인터 교환
  tmp=arr; arr=buf; buf=tmp;
 }

 // 첨에 버퍼로 할당한 공간에 최종 결과가 담겨 있으면,,, 원본 배열에 복사해 줌
 if(org != arr){
  buf=arr;
  for(i=0 ; i<n ; i++) org[i]=buf[i];
 }
 
 free(buf);
}