병합정렬(Merge sort)

병합정렬(Merge sort)

개념

정렬할 배열을 반으로 나누어 좌측과 우측 배열을 계속하여 분할해 나간 후 각 배열내에서 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘입니다.

분할 정복

큰 문제를 작은 문제 단위로 쪼개면서 해결해 나가는 방식

로직

데이터의 크기를 계속 반으로 나누고 이를 정렬하면서 다시 합치는 방법

Merge Sort는 배열의 길이가 1이하이면 이미 정렬된 것으로 본다.

정렬되지 않은 경우에

1. 분할(Divide) : 배열을 반으로 나눈다.
2. 정복(conquer) : 나누어진 배열이 여전히 분할이 가능하다면 분할을 수행한다. 그렇지 않으면 결합하여 정렬을 수행한다.
3. 결합 (combine): 두 부분의 배열을 다시 하나의 정렬된 리스트로 병합한다. 이때 결과는 임시배열에 저장된다.
4. 복사(copy) : 임시배열에 저장된 결과를 원래 배열에 복사한다.

와 같은 과정을 통해 정렬한다.

코드

MergeSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        mergeSort(0, N - 1, arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    // divide
    private static void mergeSort(int start, int end, int[] arr) {
        if (start >= end)
            return;

        int mid = (start + end) / 2;
        mergeSort(start, mid, arr); // left
        mergeSort(mid + 1, end, arr); // right

        merge(start, mid, end, arr);
    }

    // conquer
    private static void merge(int start, int mid, int end, int[] arr) {
        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;

        // combine
        while (i <= mid && j <= end) {
            if (arr[i] < arr[j])
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }
        while (i <= mid)
            temp[k++] = arr[i++];
        while (j <= end)
            temp[k++] = arr[j++];

        // copy
        while (k-- > 0)
            arr[start + k] = temp[k];
    }
}

console

정렬 전: [1, 48, 3, 51, 19, 17, 38, 64, 72, 69]
정렬 후: [1, 3, 17, 19, 38, 48, 51, 64, 69, 72]

시간복잡도

분할하는 과정에서 $O(logN)$의 시간이 병합하는 과정에서 $O(N)$의 시간이 소요된다.

최선 최악 평균 모두 $O(NlogN)$의 시간 복잡도를 갖는다.

장점

1. Quick Sort와 달리 pivot을 설정하는 방법에 따라 성능의 차이가 없이 $O(NlogN)$의 성능을 낸다.
2. 안정 정렬이다.

단점

1. 병합하는 과정에서 데이터의 개수만큼의 추가적인 공간이 필요하다.