병합 정렬 ( Merge Sort ) 이란?

안녕하세요~ 

 

오늘은 두 개의 포스팅을 연달아 합니다~

 

앞서서 선택 정렬에 대해서 알아봤는데요, 너무 쉬웠죠?

 

쉬운만큼 속도가 느린 알고리즘 중에 하나였습니다.

 

이번에는 더 빠른 알고리즘에 대해서 알아볼 겁니다.

 

바로 병합 정렬인데요, 이름에서도 알 수 있듯이 병합하면서 정렬하는 알고리즘 입니다.

 

이 알고리즘은 divide and conquer, 즉, 분할 정복 알고리즘에 기반한 알고리즘입니다.

 

일단 최소 단위로 잘게 나눈 다음에 병합하면서 정렬을 하는 것이죠.

 

어느 정도 감이 오시나요?

 

그럼 이제 그림 예제를 통해서 한 번 자세하게 알아보도록 하죠.

 

이번에도 역시 아래와 같이 정렬되지 않은 데이터 셋에서 부터 출발해 볼게요.

 

 

이제 이 데이터 셋을 반으로 나눕니다.

 

그리고 그렇게 나뉜 데이터 셋을 또 각각 반으로 나눕니다.

 

이렇게 더 이상 쪼갤 수 없을 때까지 반으로 나누고 나누고 또 나눕니다.

 

 

더 이상 쪼갤 수 없을 때 두 개 씩 병합하면서 정렬을 하기 시작합니다.

 

14와 33을 합치면서 두 데이터를 비교해서 작은 수가 왼쪽에 오도록 했습니다.

 

그리고 27과 10을 병합하면서 10을 왼쪽에 위치하도록 정렬을 했죠. 

 

이렇게 35과 19, 42와 44에 대해서도 정렬을 했습니다.

 

그리고 다시 한번 두 개의 그룹씩 합쳐서 한 그룹에 네 개의 데이터가 들어가도록 만들었습니다.

 

물론 그렇게 만들면서 각 그룹 내에서 또 정렬을 했죠.

 

 

이런 식으로 계속 병합하면서 정렬을 합니다.

 

그렇게 아래와 같이 정렬된 데이터 셋을 갖게 됩니다.

 

 

이렇게 divide and conquer 방식을 이용해서 정렬 하는 알고리즘을 병합 정렬이라고 합니다.

 

이 병합 정렬은 선택 정렬과는 달리 빠른 속도를 자랑하며, Ο(n log n)의 시간복잡도를 갖고 있습니다.

 

이렇게 말로하면 잘 모르겠다 하시는 분들이 계실 까봐 pseudo 코드를 아래 첨부합니다.

 

procedure mergesort( var a as array )    if ( n == 1 ) return a     var l1 as array = a[0] ... a[n/2]    var l2 as array = a[n/2+1] ... a[n]     l1 = mergesort( l1 )    l2 = mergesort( l2 )     return merge( l1, l2 ) end procedure  procedure merge( var a as array, var b as array )     var c as array     while ( a and b have elements )       if ( a[0] > b[0] )          add b[0] to the end of c          remove b[0] from b       else          add a[0] to the end of c          remove a[0] from a       end if    end while        while ( a has elements )       add a[0] to the end of c       remove a[0] from a    end while        while ( b has elements )       add b[0] to the end of c       remove b[0] from b    end while        return c 	 end procedure