[Algorithm Tech] 합병 정렬(Merge Sort)

* 합병 정렬(Merge Sort)    =>O(nlogn)

합병 정렬은 O(nlogn) 의 시간복잡도를 보장한다.

하지만 단점은 임시 배열 공간이 추가로 필요하다는 점이다.

분할 정복으로 구현하는데, 배열을 최대한 나누고 각 배열을 다시 정렬하면서 합병하는 방식이다.

< 작동 방식 >

1. 나눌 수 있는 만큼 끝까지 나눈다. (1개가 될때까지)

2. 나누어진 배열을 임시 배열에 저장하고 이를 비교하면서 확인한다.

모든 작동방식을 알아보는 것 보다 합치는 과정에 대표적인 예를 통해 작동방식을 알아보자.

우선 배열을 하나의 배열까지 쪼갠 후 합치면서 정렬한다.

이후 tmp 배열에 4개의 data를 복사한다.

left = start, right = mid+1로 설정하고 서로 비교해 작은 값을 data에 덮어씌운다.

left를 한칸 이동하고 작은 값을 data에 덮어씌운다.

right를 한칸 이동하고 작은 값을 data에 덮어씌운다.

right가 배열의 끝에 도달했기 때문에 남은 left를 data에 덮어씌운다.

이런 방식으로 통해 정렬하는 방식이다.

추가로, 이 방식은 left가 남았을 때만 남은 data를 덮어 씌워주면 되는데, 그 이유는 처음 시작때 임시 배열에 data를 복사했기 때문이다.

아래 예시를 살펴보자.

tmp에 data를 복사한 후 left와 right를 비교해 작은 값을 data에 넣는다.

left를 한칸 이동하고 작은 값을 data에 덮어 씌운다.

여기서 Right에 있는 값을 굳이 덮어 씌우지 않아도 원본 데이터랑 같기 때문에 Right의 경우 덮어씌울 필요가 없다.

< 소스 코드 >

public static void MergeSort(int[] num, int[] tmp, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        MergeSort(num, tmp, start, mid);
        MergeSort(num, tmp, mid + 1, end);
        Merge(num, tmp, start, mid, end);
    }
}
 
public static void Merge(int[] num, int[] tmp, int start, int mid, int end) {
    for (int i = start; i <= end; i++) {
        tmp[i] = num[i];
    }
    int left = start;
    int right = mid + 1;
    int idx = start;
    while (left <= mid && right <= end) {
        if (tmp[left] <= tmp[right]) {
            num[idx] = tmp[left];
            left++;
        } else {
            num[idx] = tmp[right];
            right++;
        }
        idx++;
    }
    //남은 left를 num 배열에 
    for (int i = 0; i <= mid - left; i++) {
        num[i + idx] = tmp[i + left];
    }
}