Merge Sort (머지 소트) 알고리즘 소개 (합치는 코드, 분할코드, 시간복잡도) : Programming Story

Merge Sort는 분할 정복 알고리즘의 하나의 종류로 N개를 효율적으로 정렬할 때 사용하는 소팅 방법이라고 할 수 있다.

예를 들어, N개의 숫자가 있고 이것을 정렬하고 싶을 때 매 단계마다 N개를 N/2, N/2개로 나누어서 각각을 정렬하는 것이다. 이렇게 분할하는 과정은 1개의 숫자가 될때까지 진행하고 1개씩 모두 나뉘어졌다면, 이제 정렬한 결과를 다시 하나로 합치는 과정을 반복한다.

MergeSort 예시로 쉽게 이해하기

예를 들어

초기 상태

위와 같은 배열을 정렬하고 싶다면, 이를 두개씩 두 그룹으로 먼저 나누는 것이다.

반으로 분할

하나의 그룹의 개수가 1개가 될때까지 분할을 계속해야 하기 때문에 한 번 더 진행해준다.

분할 한 번 더 진행

분할을 한 번 더 진행해주었더니 각 그룹의 원소 개수가 1개씩 잘 분할이 되었다. 그러면 이제 더 이상 분할할 수 없기 때문에 합치는 과정을 진행해준다. 합칠 때 정렬을 하면서 합쳐주는 것이다.

합치는 과정

위의 블락을 합치는 과정에서 정렬을 해주었다. 특히 1과 3은 원래 3, 1 순서였는데 오름차순으로 정렬하면서 1,3으로 정렬되었다. 원래 개수인 4개가 모두 합쳐질 때까지 합치는 과정을 진행해주어야 하기 때문에 한 번 더 진행해준다.

최종 정렬된 모습

두 그룹을 합치면서 순서를 정렬해주어, 최종적으로 원래 개수인 4개 숫자가 모두 오름차순으로 정렬된 것을 볼 수 있다.

합쳐주는 알고리즘 구현

그렇다면, 위에서 그림으로 설명할 때는 합치는 알고리즘을 따로 구현하지 않고 말과 그림으로만 설명했는데 코드로는 어떻게 작성할 수 있을까?

예시 그림

만약 위와 같이 start와 end가 있고 이를 합쳐야 한다고 가정해보자.

그렇다면 4개의 원소를 정렬해서 저장할 배열 하나가 추가적으로 필요하다.

저장할 배열

그러면 위와 같이 정렬된 배열을 저장할 새로운 배열을 만들어주고 여기에 정렬된 결과를 저장하면 된다. 다 저장한 이후에는 원래 배열에다가 하나씩 옮겨주면 된다.

이 합치는 과정을 코드로 한번 구현해보았다.

void merge(int start, int end){
  int mid=(start+end)/2;
  int i=start; //첫번째 그룹의 index
  int j=mid+1; //두번째 그룹의 index
  int k=0; //저장할 배열의 index
  while(i<=mid && j<=end){
   if (a[i]<=a[j]) b[k++] = a[i++]; //첫번째 그룹 수가 더 작아서 먼저 들어가야 할 경우
   else {
    b[k++]=a[j++]; 
   }
  }
  while(i<=mid) b[k++] =a[i++]; //두번째 그룹은 다 정렬되어 추가되었는데 첫번째 그룹이 다 안들어갔을 경우
  while(j<=end) b[k++] =a[j++]; //두번째 그룹이 다 안들어갔을 경우
  
  for(int i=start; i<=end; i++){
   a[i]=b[i-start]; //다시 원래 배열에 정렬된 값을 저장해줌
  }
}

두 그룹의 값을 비교하면서 말 그대로 정렬해주는 과정이다. 만약 다 정렬된 다음에 한 그룹의 숫자가 남았다면 차례대로 넣어주면 된다.

이렇게 합쳐주고 나서 이후에 다시 원래 index에 정렬된 숫자를 넣어주는 과정이 필요하다. 즉 위의 코드에서 b 배열은 임시로 정렬된 숫자를 저장하기 위해 만들어준 배열인 것이다.

분할하는 알고리즘 구현

위와 같은 과정이 분할을 한 뒤에 합치는 과정이었다면, 분할을 하는 과정의 코드는 어떻게 구현할 수 있을까?

void divide(int start, int end){
 if (start==end) return; //수의 개수가 1개면 이제 그만 분할함
 int mid=(start+end)/2; //반반 나눔
 divide(start, mid); //그 중 왼쪽
 divide(mid+1, end);  // 그 중 오른쪽 그룹
 merge(start, end); //이후 둘을 합침 (위에서 작성한 merge 함수 호출)
}

이렇게 재귀적으로 mid를 기준으로 왼쪽 오른쪽 그룹을 나누어서 결국 그룹의 수가 1개가 될때까지 divide를 실행해준다. 그런 다음에 merge 함수를 호출해서 divide한 그룹을 다시 정렬하면서 합쳐준다.

MergeSort의 시간복잡도 : O(nlogn)

계속 반씩 나누어서 divide를 해주기 때문에 기본적으로 O(logN)의 시간복잡도를 가지고 있고, 거기에 추가하여서 합치는 과정이 O(N)의 시간복잡도를 갖기 때문에 전체적으로 MergeSort는 O(nlogn)의 시간복잡도를 가지고 있다고 할 수 있다.