개발자로 살아남기

합병(병합) 정렬 (Merge Sort)

합병(병합) 정렬 (Merge Sort)

• 안정 정렬 (stable sort)
   - 정렬 후에도 같은 값들끼리의 순서가 보장됨을 의미함
  ex) 5, 4, 3(A), 2, 3(B), 1
        1, 2, 3(A), 3(B), 4, 5
• 분할정복 (divide and conquer) 알고리즘 중 하나
• 정렬 시 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)가 될 수 없음

합병 정렬 방법

1. 분할 (divide) : 데이터 리스트에서 데이터가 하나씩 정렬될 때까지 리스트를 절반씩 나눈다.
2. 정복 (conquer) : 나눈 데이터들끼리 재귀적으로 정렬을 진행한다.
3. 결합 (combine) : 정렬된 데이터들을 하나로 합친다.

성능

• 시간복잡도
  최악의 경우 : O(n log2(n))
  최선의 경우 : O(n log2(n))
  

  

• 분할
  데이터의 개수가 8개라고 했을 때 3번의 분할과정을 통해 8 -> 4 -> 2 -> 1 (2^3 -> 2^2 -> 2^1 -> 2^0) 순으로 줄어들게 된다. 따라서 분할과정은 3 = log2(8)이 되므로 결국 분할횟수 = log2(데이터 개수) 가 된다.
• 정복 및 결합
  데이터 8개를 2개씩 결합하면 총 4개의 덩어리가 나오게 되며 데이터마다 비교하게 되면 최대 2번 비교하게 된다. 따라서 데이터 2개와 4개의 덩어리를 곱하면 최대 8번의 비교 횟수가 나온다. 다시 데이터 4개와 2개의 덩어리를 곱하면 8번이 되므로 각 병합의 단계마다 최대 데이터 개수만큼 비교하게 되어 병합 횟수 = 데이터 개수가 된다.

구현

• 기본 구현
  [MergeBasic.java]
  

  package Sort.Merge;
  
  public class MergeBasic {
      public static void sort(int[] arr, int left, int right) {
          mergeSort(arr, left, right);
      }
  
      private static void mergeSort(int[] arr, int left, int right) {
          int mid = 0;
          if (left < right) {
              mid = (left + right) / 2; // 데이터 리스트의 중앙 인덱스를 구함
              mergeSort(arr, left, mid); // 중앙을 기준으로 왼쪽 데이터들을 분할한다.
              mergeSort(arr, mid + 1, right); // 중앙을 기준으로 오른쪽 데이터들을 분할한다.
              merge(arr, left, mid, right); // 정복 및 결합 과정을 진행한다.
          }
      }
  
      private static void merge(int[] arr, int left, int mid, int right) {
          // 분할된 왼쪽 리스트들의 시작점 변수
          int leftIndex = left;
          // 분할된 오른쪽 리스트들의 시작점 변수
          int rightIndex = mid + 1;
          // 정렬된 데이터가 저장될 인덱스
          int sortedIndex = left;
          // 정렬된 데이터를 임시로 저장할 곳
          int[] tmpSortedArray = new int[right + 1];
  
          // 분할된 왼쪽 리스트의 인덱스가 mid까지 온 경우 왼쪽 정렬 완료
          // 분할된 오른쪽 리스트의 인덱스가 right까지 온 경우 오른쪽 정렬 완료
          // 즉, 왼쪽 또는 오른쪽 둘 중 하나라도 정렬이 완료된 경우 반복문을 빠져나감
          while(leftIndex <= mid && rightIndex <= right) {
              // 오름차순 조건문
              if (arr[leftIndex] <= arr[rightIndex]) {
                  tmpSortedArray[sortedIndex++] = arr[leftIndex++];
              }
              else {
                  tmpSortedArray[sortedIndex++] = arr[rightIndex++];
              }
          }
  
          // 왼쪽이 다 정렬된 경우 오른쪽 데이터들의 남은 부분들을 다 옮겨야 함
          if (leftIndex > mid) {
              for(int i=rightIndex; i<=right; i++) {
                  tmpSortedArray[sortedIndex++] = arr[i];
              }
          }
          else {
              for(int i=leftIndex; i<=mid; i++) {
                  tmpSortedArray[sortedIndex++] = arr[i];
              }
          }
  
          // 원래 배열에 정렬된 데이터로 덮어씌움
          for(int i=left; i<=right; i++) {
              arr[i] = tmpSortedArray[i];
          }
      }
  }

• 테스트
  [MergeBasicMain.java]
  

  package Sort.Merge;
  
  public class MergeBasicMain {
      private static final int MAX_COUNT = 30;
  
      public static void main(String[] args) {
          int[] arr = new int[MAX_COUNT];
          for(int i=0; i<MAX_COUNT; i++) {
              // 0 ~ MAX_COUNT 범위내의 난수를 생성
              arr[i] = (int)(Math.random() * MAX_COUNT);
          }
  
          System.out.println("정렬 전 데이터");
          for(int i : arr) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          int[] ascSortedArrayTest = arr.clone();
          MergeBasic.sort(ascSortedArrayTest, 0, ascSortedArrayTest.length - 1);
          for(int i : ascSortedArrayTest) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
  }​

• 결과
  

  

참고

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

윤성우의 열혈 자료구조