합병 정렬

시간 계산이 빠른 정렬 중에 하나입니다.

분할 정복 (큰 문제를 작은 문제로 쪼개 해결해 나가는 방법)을 통해 구현한 정렬입니다.

 

합병 정렬은 3가지 과정을 거쳐 정렬을 완료합니다.

과정

• 분할 (Divide) - 입력 배열을 비슷한 크기의 2개의 부분 배열로 분할합니다.
• 정복 (Conquer) - 크기가 충분히 작아질 때 까지 분할된 부분 배열을 정렬합니다. 
• 결합 (Combine) - 정렬된 부분 배열들을 하나의 배열에 다시 결합합니다.

특징

• 분할 정복 알고리즘
• 안정 정렬
• 배열로 구성할 시에, 임시 배열이 필요할 수 있다
• 연결 리스트로 구성하면, 데이터에 이동은 무시할 수 있다. - 제자리 정렬이라고도 할 수 있음
• 연결 리스트 시에 최고의 정렬 방법

복잡도

• 최악: O (nlogn)
• 최선: O (nlogn)
• 평균: O (nlogn)

굉장히 효율적인 편입니다.

예시 그림

구현 코드 ( java )

void mergeSort(int[] arr) {
	sort(arr, 0, arr.length);
}

void sort(int[] arr, int low, int high) {
  if (high - low < 2) {
  	return;
  }

  int mid = (low + high) / 2;
  sort(arr, 0, mid);
  sort(arr, mid, high);
  merge(arr, low, mid, high);
}

private static void merge(int[] arr, int low, int mid, int high) {
  int[] temp = new int[high - low];
  int t = 0, l = low, h = mid;

  while (l < mid && h < high) {
      if (arr[l] < arr[h]) {
        temp[t++] = arr[l++];
      } else {
        temp[t++] = arr[h++];
      }
    }

  while (l < mid) {
  	temp[t++] = arr[l++];
  }

  while (h < high) {
  	temp[t++] = arr[h++];
  }

  for (int i = low; i < high; i++) {
  	arr[i] = temp[i - low];
  }
}