Merge Sort (합병 정렬)

분할 정복 (Divide and Conquer) 메서드의 기초 알고리즘 중 하나다. Insertion Sort랑 같은 목표 (배열을 정렬하기)를 갖고 있지만 과정은 Insertion Sort보다 많다. 배열을 계속 반복적으로 둘로 분할한다 한 개씩 남을 때 까지. 정복하는 과정은 여기서 부터 시작된다. 먼저 방금전 까지 나누어진 배열 요소들 끼리 정렬한 다음에 반복적으로 Insertion Sort와 같은 방식으로 정렬 시켜서 왼쪽과 오른쪽 배열들을 만든다. 왼쪽 배열에 소속이 되있는 요소들과 오른쪽 배열에 소속이 되있는 요소들 끼리 비교하면서 정렬하고 합치면 정렬된 배열이 완전체가 된다.

위 설명을 못 알아들었으면 비주얼을 참고하자.

메서드: 분할 정복 (Divide and Conquer)

 

의사코드는 다음과 같다.

 

  Merge(A,l,m,r)  
    n1 = m - l + 1  
    n2 = r - m  
    let L\[1..n1 + 1\] and R\[1..n2 + 1\] be new arrays  
    for i = 1 to n1  
      L\[i\] = A\[l + i - 1\]  
    for j = 1 to n2  
      R\[j\] = A\[m + j\]  
    L\[n1 + 1\] = infinity  
    R\[n2 + 1\] = infimity  
    i = 1  
    j = 1  
    for k = l to r  
      if L\[i\] <= R\[j\]  
        A\[k\] = L\[i\]  
        i++  
      else   
        A\[k\] = R\[j\]  
        j++          

 

의사코드 두개가 주어졌는데 첫번째 Merge 알고리즘은 나누어진 배열들을 정복하고 정렬한다. 아래의 Merge-Sort 알고리즘은 오리지널 배열을 recursion을 이용해 반복적으로 나누는 역할을 맡는다.

 

  Merge-Sort(Array,l,r)  
    if l < r  
      middle m = \[(l + r)/2\]  
      Merge-Sort(Array,l,m)  
      Merge-Sort(Array,m + 1,r)  
      Merge(A,l,m,r)  

 

총 시간 복잡도는 O(nLogn)이다. 배열을 반복적으로 분할하는 시간이 n/2씩이나 걸리며 정령하는 시간은 선형적인 O(n)시간이 걸린다. 공간 복잡도 마저 O(n) 만큼 소요된다.

여기서 중요한 점은 Insertion Sort와 Merge Sort의 차이점이다. 입력 사이즈가 클 수록 Merge Sort 알고리즘이 Insertion Sort보다 빠른 시간 내에 배열을 정렬하는데 대신 입력 사이즈가 작을 수록 Insertion Sort가 Merge Sort 알고리즘 보다 더 적은 시간 내에 배열을 정렬한다.

아래 깃허브 레포지토리에 Merge Sort 알고리즘을 응용한 프로그램을 작성했다. 주석도 추가했으니 참고하는 것도 나쁘지는 않을 것 같다.

 

 

yoonBot/Computer-Science-and-Engineering