[알고리즘] 병합 정렬 (Merge Sort)

목차

병합 정렬이란?

병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘이다. 추가로 병합 정렬은 퀵 정렬과 달리 정렬을 할 때 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)이 될 수는 없다.

 

병합 정렬은 분할 정복의 다음과 같은 과정을 거친다.

 

분할(Divide) : 리스트를 두 개의 리스트로 분할한다

정복(Conquer) : 분할된 리스트를 정렬한다. 

결합(Combine): 정렬된 두 개의 리스트를 하나의 정렬된 리스트로 결합한다.

 

이제 병합 정렬의 예시를 한번 살펴보겠다.

 

 

병합 정렬 병합 과정

분할된 리스트를 하나의 정렬된 리스트로 합칠 때 정렬을 하면서 합치게 된다. 그리고 이때 걸리는 시간 복잡도는 O(N)이다. 이 이유는 이미 정렬된 리스트들을 합치기 때문이다. 조금 더 구체적으로 병합하는 과정을 살펴보도록 하겠다.

 

1. 두 개의 리스트의 값을 처음부터 비교해서 두 개의 리스트의 값 중에 작은 값을 새로운 리스트로 옮긴다.

2. 두 개의 리스트 중 하나의 리스트가 끝날 때까지 반복한다.

3. 하나의 리스트가 끝나게 되면 남은 리스트의 값을 모두 새로운 리스트로 옮긴다.

 

 

 

소스 코드

 

import java.io.*;
import java.util.*;
public class Main {
    static int number = 15;  //데이터 개수
    static int[] sorted = new int[number];  //정렬된 배열

    static void merge(int[] a, int m, int mid, int n) {
        int i = m;
        int j = mid + 1;
        int k = m;
        // 두 배열 중 하나를 다 옮길 때 까지 반복
        while (i <= mid && j <= n) {
            if (a[i] < a[j]) {
                sorted[k] = a[i];
                i++;
            } else {
                sorted[k] = a[j];
                j++;
            }
            k++;
        }

        //남아있는 데이터 삽입
        if (i > mid) {
            for (int t = j; t <= n; t++) {
                sorted[k] = a[t];
                k++;
            }
        } else {
            for (int t = i; t <= mid; t++) {
                sorted[k] = a[t];
                k++;
            }
        }

        //정렬된 배열을 기존 배열에 삽입
        for (int t = m; t <= n; t++) {
            a[t] = sorted[t];
        }
    }

    static void mergeSort(int[] a, int m, int n) {
        if (m < n) {
            int mid = (m + n) / 2;  //배열의 중간간
            mergeSort(a, m, mid);
            mergeSort(a, mid + 1, n);
            merge(a, m, mid, n);
        }
    }
    
    public static void main(String[] args) throws IOException {
        int[] arr = {1, 5, 10, 12, 4, 3, 8, 9, 11, 2, 13, 15, 6, 14, 7};  //정렬할 배열
        mergeSort(arr, 0, arr.length-1);
        for (int i = 0; i < number; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

이제 이 코드를 이용해서 다음과 같은 배열을 정렬해보겠다

 

배열 = {1, 5, 10, 12, 4, 3, 8, 9, 11, 2, 13, 15, 6, 14, 7};

 

 

즉, 다음과 같이 1부터 15까지 정렬되어 있는 것을 확인할 수 있다.

 

 

병합 정렬 시간 복잡도

 

 

병합 정렬의 시간 복잡도는 n개의 데이터를 가지고 logN단계를 거치기 때문에 O(NlogN)이 된다. 퀵 정렬은 피봇을 어떻게 선택하느냐에 따라 최악의 시간 복잡도가 O(N^2)가 되지만 병합 정렬은 항상 리스트를 절반으로 나누기 때문에 O(NlogN)의 시간 복잡도를 보장한다.

 

 

병합 정렬 장단점

장점

• 퀵 정렬은 데이터의 분포에 따라 최악의 경우 O(n2)의 시간 복잡도를 갖는데 병합 정렬은 O(nlogn)의 시간 복잡도를 보장한다
• 선택 정렬, 삽입 정렬같이 O(n2)의 시간 복잡도를 가지고 있는 정렬 알고리즘보다 더 효율적이다

 

단점

• 데이터가 배열로 구성된 경우 임시 배열이 필요하므로 추가 공간이 필요하다. → 추가 공간을 사용하므로 제자리 정렬이 아니다
• 데이터의 크기가 큰 경우 이동 횟수가 많으므로 시간 낭비 발생