[ Algorithm ] Merge Sort(병합 정렬)

병합 정렬(Merge Sort)#

작동 원리#

정렬된 배열 합치기(Merging Sorted Arrays)#

다음과 같이 정렬된 두 배열을 합친다고 해보자.

그리고 두 배열의 요소가 들어갈 수 있는 배열 하나를 만든다.

그리고 두 배열중 큰 값을 비교한다.

그리고 둘 중 작은 값을 새로 생성한 배열에 넣는다. 그리고 넣은 값이 있는 배열의 피봇을 하나 오른쪽으로 이동시킨다.

이후, 두 값을 비교하여 작은 값을 넣는다.

똑같이 반복하면, 두 배열을 합친 정렬된 배열을 볼 수 있다.

정렬된 배열을 합치는 과정은 매우 효율적이다.

시간 복잡도(Time complexity): O(N)
공간 복잡도(Space complexity): O(N) (추가 배열 생성)

이는 정렬된 데이터에 사용할 수 있는 효율적 알고리즘의 간단한 예시이다.

정렬된 배열들의 필요성#

병합 정렬은 원본 배열을 정렬된 여러 배열로 분할하는 방식으로 동작한다. 이 과정에서 원본 배열을 직접 정렬하지 않고, 대신 입력 배열을 재귀적으로 반씩 나누어 요소가 1개인 배열들을 만든다. 요소가 1개인 배열은 자동으로 정렬된 상태이며, 정확히 반씩 나누므로 재귀 깊이는 O(log N)이 된다. 그 후 재귀의 반대 방향으로 진행하면서 배열들을 정렬된 상태로 합쳐나가는데, 각 재귀 단계에서 방문하는 요소 수는 O(N)이다. 최종적으로 가장 상위 단계까지 배열을 합치면 전체 정렬이 완료된다.

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)#

평균 수행 시간: $O(NlogN)$
최악 수행 시간: $O(NlogN)$
메모리(공간 복잡도): $O(N)$
안정성: O

코드#

public class MergeSort implements Sort{  
    @Override  
    public int[] sort(int[] array) {  
        if (array == null) {  
            return array;  
        }  
  
        if (array.length > 1) {  
            int mid = array.length / 2;  
            int[] leftArray = new int[mid];  
            int[] rightArray = new int[array.length - mid];  
  
            System.arraycopy(array, 0, leftArray, 0, mid);  
            System.arraycopy(array, mid, rightArray, 0, array.length - mid);  
  
            sort(leftArray);  
            sort(rightArray);  
            merge(array, leftArray, rightArray);  
        }  
        return array;  
    }  
  
    public static void merge(int[] array, int[] leftArray, int[] rightArray) {  
        int leftIndex = 0, rightIndex = 0, mergedIndex = 0;  
  
        // 왼쪽과 오른쪽 배열을 비교, 그중 작은 값을 먼저 병합  
        while (leftIndex < leftArray.length && rightIndex < rightArray.length) {  
            if (leftArray[leftIndex] < rightArray[rightIndex]) {  
                array[mergedIndex++] = leftArray[leftIndex++];  
            } else {  
                array[mergedIndex++] = rightArray[rightIndex++];  
            }  
        }  
  
        // 남은 요소들 처리  
        while (leftIndex < leftArray.length) {  
            array[mergedIndex++] = leftArray[leftIndex++];  
        }  
  
        while (rightIndex < rightArray.length) {  
            array[mergedIndex++] = rightArray[rightIndex++];  
        }  
    }  
}