[정렬 연습] 병합 정렬의 원리 및 구현 - Java

병합 정렬이란?

병합 정렬은 퀵 정렬과 마찬가지로 분할 정복 알고리즘으로서 주어진 데이터를 두 개의 균등한 크기로 분할하고 분할된 영역을 정렬한 후 병합해 나가는 방식으로 정렬한다. 이때 분할하고 병합하는 과정에서 기존 데이터 전체 크기와 동일한 추가적인 자료구조를 사용하므로 O(n)의 공간 복잡도를 가진다.

 

그림으로 병합 정렬 이해하기

아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 병합 정렬을 통해 오름차순으로 정렬해보자.

 

 

우선, 주어진 배열의 영역을 절반씩 분할해나가는데, 영역의 크기가 2개 이하가 될 때까지 분할해나간다. 이때 분할해나가는 과정은 마치 깊이 우선 탐색과도 같다.

 

 

 

분할을 해나가는 중 영역의 크기가 2개 이하가 됐을 경우 즉, 더 이상 분할할 게 없는 경우 해당 영역을 정렬 및 병합하고, 부모가 같은 분할된 형제 영역 역시 동일한 방식으로 정렬 및 병합한다. 참고로 이 과정에서 기존 배열과 동일한 크기의 임시 배열을 이용한다.

 

※ 실제론 크기 1의 영역은 별도로 정렬 및 병합 작업을 수행하지 않는다.

 

그 다음 이 두 형제 영역을 다시 정렬 및 병합하면서 정렬된 부모 영역을 만들고, 그 부모 영역의 형제 영역도 앞선 작업들을 반복함으로써 최종적으로 원본 배열에 정렬된 배열이 저장되게 된다.

 

 

자바로 병합 정렬 구현하기

앞선 원리를 적용해 병합 정렬을 자바로 구현해보면 다음과 같다.

 

public class MergeSort {

    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];
        mergeSort(array, temp, 0, array.length - 1);
    }

    private static void mergeSort(int[] array, int[] temp, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(array, temp, start, mid);
            mergeSort(array, temp, mid + 1, end);
            merge(array, temp, start, mid, end);
        }
    }

    private static void merge(int[] array, int[] temp, int start, int mid, int end) {
        System.arraycopy(array, start, temp, start, end - start + 1);

        int part1 = start;
        int part2 = mid + 1;
        int index = start;
        while (part1 <= mid && part2 <= end) {
            if (temp[part1] <= temp[part2]) { // temp[part1] > temp[part2] 로 설정 시 내림차순
                array[index++] = temp[part1++];
            } else {
                array[index++] = temp[part2++];
            }
        }

        if (mid - part1 + 1 >= 0)
            System.arraycopy(temp, part1, array, index, mid - part1 + 1);
    }
}

 

병합 정렬의 성능

병합정렬은 주어진 N개의 데이터를 N번 만큼 나누는데, 나눌 때마다 검색해야하는 데이터가 절반씩 줄어들기 때문에 시간 복잡도는 O(N * log N)이라고 생각할 수 있다. 다만, 정렬하고 병합하는 과정에서 임시 배열이 사용되어 공간 복잡도는 O(N)을 가진다.

 

또한 퀵 정렬의 경우 피벗 설정에 따라 최악의 경우 O(N^2)의 시간 복잡도를 가졌지만, 병합 정렬은 특정 기준과 상관없이 절반씩 분할되며 정렬 및 병합 과정이 일어나므로 O(N * log N)의 시간 복잡도를 보장한다.

 

성능 비교를 위해 다음과 같이 3만개의 무작위 정수형 배열로 '버블 정렬', '선택 정렬', '삽입 정렬', '호어 분할 방식의 퀵 정렬', '병합 정렬'의 실행 시간을 각각 측정해보았다.

 

        int[] array2 = new int[30000];
        Random random = new Random(30000);
        for (int i = 0; i < 30000; i++) {
            array2[i] = random.nextInt(30000);
        }

 

실행 결과

 

실행 결과 퀵 정렬과 비슷한 성능을 보이는 것을 확인할 수 있었다.

 

오름차순으로 정렬된 16500개의 정수형 배열에 대해서도 성능을 비교해보자.

 

        int[] array1 = new int[16500];
        for (int i = 0; i < 16500; i++) {
            array1[i] = i;
        }

 

실행 결과

 

정렬된 데이터에 대해서 최악의 성능을 보이는 퀵 정렬(첫 번째 데이터를 피벗으로 설정)과 달리 병합 정렬은 정렬된 데이터를 정렬함에 있어서도 삽입 정렬에 준하는 성능을 나타냈다.

 

아울러, 다음과 같은 4만개의 무작위 정수형 배열을 기준으로 자바의 Arrays 클래스에서 제공하는 sort 메서드의 성능을 비교해보았다.

 

        int[] array2 = new int[40000];
        Random random = new Random(40000);
        for (int i = 0; i < 40000; i++) {
            array2[i] = random.nextInt(40000);
        }

 

실행 결과

 

실행 결과 유의미한 차이는 나지 않았다. 참고로 실제 자바 Arrays 클래스의 정렬 API(sort 메서드)는 시간복잡도 O(n logn)의 Dual-Pivot 퀵 정렬 알고리즘을 기반으로 구현되어 있다고 한다.

 

참고자료

• 유튜브 엔지니어대한민국