[Algorithm] 병합 정렬(Merge Sort)

1. 병합 정렬(Merge Sort)이란?

• 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘
• 배열 병합의 시간 복잡도는 O(n)이고, 전체 시간 복잡도는 O(n log n)이다.
• 서로 떨어져있는 요소를 교환하는 경우가 없으므로 안정적인 정렬 방법이다.

이미지 출처: https://www.researchgate.net/profile/Akande-Oluwatobi-2/publication/341900290/figure/fig1/AS:898574221058048@1591248197000/Example-Illustrating-Merge-Sort-Operation-For-instance-with-a-list-containing-elements.png

2. 동작 방식

int[] arr = { 5,6,4,8,3,7,9,0 };

// 1. 배열을 앞부분과 뒷부분으로 나눈다. 
앞부분(a): { 5,6,4,8 }
뒷부분(b): { 3,7,9,0 }

// 2. 앞부분과 뒷부분을 재귀를 사용하여 정렬한다.
앞부분(a): { 4,5,6,8 }
뒷부분(b): { 0,3,7,9 }
정렬된 배열(c): {}

// 3. 각 배열의 작업에서 선택한 요소의 인덱스는 pa, pb, pc이다.
// 4. 배열 앞부분에서 선택한 요소와 배열 뒷부분에서 선택한 요소를 비교하여 작은쪽 값을 배열에 저장한다.
// 5. pa, pb가 가리키는 값을 비교하여 작은 쪽값을 꺼내 c[pc]에 대입하고 꺼낸 쪽의 커서와 배열 c의 커서 pc를 한칸 나아가도록 하는 작업을 반복한다.

3. 구현하기

public class MergeSort {
  static int[] buff;

  private static void __mergeSort(int[] arr,int start, int end) {
    if(start < end) {
      int i;
      int center = (start + end) / 2;
      int p = 0; // buff의 개수
      int j = 0; // buff의 인덱스
      int k = start; // 정렬된 배열 arr의 인덱스

      __mergeSort(arr, start, center); // 배열의 앞부분 정렬
      __mergeSort(arr, center + 1, end); // 배열의 뒷부분 정렬

      // 배열의 앞부분을 buff에 복사
      for(i = start; i <= center; i++) {
        buff[p++] = arr[i];
      }

      // 배열의 뒷부분과 buff에 복사한 배열의 앞부분 p개를 병합한 결과를 배열 arr에 저장
      while(i <= end && j < p) {
        arr[k++] = (buff[j] <= arr[i] ? buff[j++] : arr[i++]);
      }

      // 배열 buff에 남아있는 요소를 arr에 복사
      while(j < p) {
        arr[k++] = buff[j++];
      }
    }
  }

  private static void mergeSort(int[] arr) {
    buff = new int[arr.length];
    __mergeSort(arr, 0, arr.length - 1);
    buff = null;
  }

  public static void main(String[] args) {
    int[] arr = { 5,6,4,8,3,7,9,0 };
    mergeSort(arr);
  }
}