[Algorithm] Merge Sort(병합 정렬)

[Algorithm] Merge Sort(병합 정렬)

1. 정의

• 데이터 배열의 원소를 반으로 나누고, 합쳐서 정렬하는 알고리즘
• 분할 정복을 사용
• 시간 복잡도
  • 최선 : $O(nlogn)$
  • 평균 : $O(nlogn)$
  • 최악 : $O(nlogn)$

2. 동작 과정

1. 배열의 원소가 2개가 남을 때까지 이등분 한다.
2. 2개의 원소를 반으로 나누어 각각 비교하여 정렬된 배열을 얻는다.
3. 나머지 배열들을 병합하면서 정렬한다.

3. 장단점

• 장점
  • 순차적인 비교로 정렬
  • 일정한 속도
  • 안정 정렬
  • LinkedList 정렬할 때 퀵 정렬 보다 효율이 좋음
    • LinkedList는 순차 접근을 해야하는데 퀵 정렬은 임의 접근이기 때문
• 단점
  • 추가적인 공간이 필요

4. 코드

public void mergeSort(int[] arr, int left,  int right) {
   if (left < right) {
      int mid = (left + right) / 2;

      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);
      merge(array, left, mid, right);
   }
}

public static void merge(int[] arr, int left, int mid, int right) {
   int[] L = Arrays.copyOfRange(arr, left, mid + 1);
   int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);

   int i = 0;
   int j = 0;
   int k = left;
   int ll = L.length;
   int rl = R.length;

   while (i < ll && j < rl) {
      if (L[i] <= R[j]) {
         arr[k++] = L[i++];
      } else {
         arr[k++] = R[j++];
      }
   }

   //다 탐색하고도 한 쪽이 남으면
   while(i < ll) { //왼쪽이 남았을 때
      arr[k++] = L[i++];
   }

   while(j < rl) { //오른쪽이 남았을 때
      arr[k++] = R[j++];
   }
}

---

※ 참고

• tech-interview-for-developer/Algorithm/MergeSort
• [알고리즘] 병합 정렬 알고리즘 (Merge Sort)