[Algorism] 합병정렬(Merge Sort)

정렬 알고리즘은 다양하게 존재합니다.
대표적은 정렬 알고리즘인 합병정렬은 분할정복법를 사용하는 Sort 알고리즘입니다.

 

 

분할정복법은 분할, 정복, 합병으로 나눠 작업 합니다.

• 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

• 정복 : 각각의 작은 문제를 순환적으로 해결

• 합병 : 작은 문제의 해를 합하여(merge) 원래 문제를 대한 해를 구함

 

Merge sort는 두 배열을 합병정렬하는 방법입니다.
그림을 참고하시면 좀 더 이해하기 편하실 것입니다.

• 수도코드

  mergeSort(A[], p, r)  //A[p ... r] 을 정렬한다
  {
      if (p < r) then {
          q <- (p+r) / 2;     // p, r의 중간 지점 계산
          mergeSort(A, p, q);
          mergeSort(A, q+1. r);
          merge(A, p, q, r);
      }
  }
  
  merge(A[] , p, q, r)
  {
      정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 합하여 
      정렬된 하나의 배열 A[p...r]을 만든다
  }

• 소스코드
  merge_sort.java

  /*
  * 두 배열을 합치는 메소드
  * data[] 정렬할 배열, p는 시작 index, q는 중간 index, r은 마지막 index
  */
  void merge(int data[], int p, int q, int r){
      int i = p, j = q+1, k = p;
      int tmp[data.length()];
      // q을 기준으로 앞 배열과 뒤 배열 중 k 배열로 모두 옮겨질 때까지 반복
      while (i <= q && j <= r){
          if(data[i] <= data[j])
              tmp[k++] = data[i++];
          else
              tmp[k++] = data[j++];
      }
  
      while (i <= q)
          tmp[k++] = data[i++];
      while (k <= r)
          tmp[k++] = data[j++];
      // 정렬된 데이터를 원래 데이터로 옮겨준다.
      for(int i = p, i <= r; i++)
          data[i] = tmp[i];
  }
  
  /**
  * 정렬
  * data[] 정렬할 배열, p는 시작 index, r은 마지막 index
  */
  void mergeSort(int data[], int p, int r{
      int q;
      if(p < r){
          q = (p + r) / 2;
  
          mergeSort(data[], p, q);
          mergeSort(data[], q + 1, r);
          merge(data[], p, q, r);
      }
  }

 

합병정렬의 단점

• 추가적은 배열을 만들어야 합니다.

• 정렬할 레코드의 크기가 클 경우 시간적 낭비를 초래합니다.

 

시간복잡도

시간복잡도는 nlogn으로 구성됩니다.

T(n) = 0                           // if n = 1
T(n) = T(n/2) + T(n+2) + n         //otherwise
     = O(nlogn)

 

 

정리

합병 정렬(Merge Sort)에 대해서 알아봤습니다.

nlogn의 시간복잡도를 갖은 정렬 알고리즘만큼 빠르게 정렬되는 알고리즘입니다.

 

 

참고사항

합병정렬이란? - heejeong Kwon님의 글

합병정렬 - 위키백과