병합정렬(Merge Sort)

데이터 집합을 절반으로 쪼개어 나간 뒤 쪼개진 부분집합들을 다시 정렬된 형태로 합치는 방식의 분할정복 정렬

https://ko.wikipedia.org/wiki/합병_정렬

 

시간 복잡도

데이터를 균등하게 절반씩 쪼개나가기에 총 n개의 데이터가 logn 단계만큼의 연산을 수행하므로 O(NLogN)이 된다.

 

공간 복잡도

데이터를 정렬함에 있어 추가적인 데이터 리스트 공간이 필요하기 때문에 O(n)의 공간 복잡도를 가지지만 다른 정렬보다 n만큼의 메모리를 더 차지하게 된다.

 

Code

public class MergeSort {
    public static void mergeSort(int[] data) {

        if (data.length < 2) {
            return;
        }

        int mid = data.length / 2;
        int[] tempLeft = new int[mid];
        int[] tempRight = new int[data.length - mid];

        System.arraycopy(data, 0, tempLeft, 0, tempLeft.length);
        System.arraycopy(data, mid, tempRight, 0, tempRight.length);

        mergeSort(tempLeft);
        mergeSort(tempRight);

        merge(data, tempLeft, tempRight);
    }

    private static void merge(int[] data, int[] tempLeft, int[] tempRight) {
        int leftIdx = 0;
        int rightIdx = 0;
        int dataIdx = 0;

        while (leftIdx < tempLeft.length && rightIdx < tempRight.length) {
            if (tempLeft[leftIdx] < tempRight[rightIdx]) {
                data[dataIdx++] = tempLeft[leftIdx++];
            } else {
                data[dataIdx++] = tempRight[rightIdx++];
            }
        }

        while (leftIdx < tempLeft.length) {
            data[dataIdx++] = tempLeft[leftIdx++];
        }

        while (rightIdx < tempRight.length) {
            data[dataIdx++] = tempRight[rightIdx++];
        }

    }
}

 

퀵정렬과 비교

1. Bottom-up vs Top-down

• 퀵정렬 (Top-down)
  • 피봇을 중심으로 작은집합, 큰 집합으로 나누어 정렬함으로서 큰 문제에서 작은 문제로 내려가는 문제해결 방식을 보인다.

• 병합정렬 (Bottom-up)
  • 우선 데이터를 모두 쪼갠 뒤 하나씩 합쳐나가며 정렬함으로서 작은 문제에서 큰 문제로 올라가는 문제해결 방식을 보인다.

2. 속도

• 퀵정렬은 최악의 경우 O(n^2)의 시간복잡도를 가지게 되지만 피봇을 중심으로 순차적으로 데이터를 탐색해서 swap을 하기 때문에 공간적 locality 측면에서 cache hit율이 높으므로 병합정렬보다 속도가 더 빠르다.
• 병합정렬은 정렬을 할때마다 새로운 공간을 만들어야 하기 때문에 새로운 공간을 만드는 과정에서 속도가 더 느려지게 된다.