병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

병합 정렬 이란?

• 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현
• 안정 정렬 이다

---

Process

1. 원소 개수가 1 또는 0 이 될 때 까지 두 부분으로 쪼갠다
2. 쪼갠 순서의 역순으로 크기를 비교해 병합해 나간다

---

Java Code

import java.util.*;
public class Main {

    public static void main(String[] args) {
        int[] arr = {43, 51, 76, 60, 73, 82, 36, 98,10,23,1,100};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int l, int r){
        if(l < r){
            int m = (l+r)/2;

            mergeSort(arr, l, m); // 분할
            mergeSort(arr, m+1, r); // 분할
            merge(arr, l, m, r); // 정복
        }
    }

    public static void merge(int[] arr, int l, int m, int r){
        int[] L = Arrays.copyOfRange(arr, l , m+1); // 임시 배열에 복사
        int[] R = Arrays.copyOfRange(arr, m+1, r+1); // 임시 배열에 복사

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

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

        while(i < ll){
            arr[k++] = L[i++];
        }

        while(j < rl){
            arr[k++] = R[j++];
        }

    }

}

---

Merge Sort GIF

---

시간복잡도

Always : O(nlog₂n)

• 분할 과정 : O(log₂n)
• 정복 과정(merge) : O(N)
• 따라서 분할과정 * 정복과정 = O(nlog₂n)

---

장점

• Quick Sort 와 달리 어떠한 상황에서도 O(nlog₂n)의 시간 복잡도를 보장한다
• 안정 정렬 이다
  • 안정 정렬 : 입력한 순서가 보장 되는 정렬

단점

• 데이터 크기만한 메모리가 추가적으로 필요하다
• 임시 배열에 원본 배열의 복사가 필요하므로, 배열의 크기가 상당히 큰 경우 오버헤드가 크다

---

참고

• 병합 정렬
• 정렬 알고리즘 - 병합 정렬(Merge sort)