합병 정렬(Merge Sort)

합병정렬은 분할 정복(Divide and Conquer) 알고리즘을 이용하여 푸는 방식이다.

 

1. 먼저, 주어진 배열을 절반의 크기로 나누는데 그 크기가 2짜리 배열이 될 때까지 계속해서 반복한다.

 

2. 이후, 길이가 2인 각 배열들 내에서 크기 순으로 정렬하고, 이웃한 2개의 배열을 합쳐서 또 정렬한다. 이를 모든 배열들이 합쳐져 원래 크기의 배열의 길이가 될 때까지 반복한다.

 

3. 이때, 정렬은 다음과 같은 방식으로 진행한다.

ex) arr[0~3] arr[4~7]을 비교하여 정렬 시.

arr[0]와 arr[4]를 비교하고 작은 수를 먼저 temp[0~7]라는 임의의 배열의 temp[0]에 넣는다.

그 수가 만약 arr[0]이었다면, 다음엔 arr[1]과 arr[4]를 비교한다.

이런 식으로, 두 배열의 처음부터 끝까지 넣는데 만약 한쪽 배열들의 element들이 다 temp배열에 넣어졌다면, 나머지 temp부분들은 다른 배열의 element들로 채운다.

 

합병정렬을 코드로 구현하면 다음과 같다.

 

import java.io.*;

class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int [] arr = new int [num];
        for(int i=0; i<num; i++) arr[i] = Integer.parseInt(br.readLine());
        mergeSort(arr, 0, num-1);
        for(int i=0; i<num; i++) System.out.println(arr[i]+" ");
    }

    public static void mergeSort(int[] A, int p, int r){ //원래 배열을 크기가 1이 되기 전까지 이분할해주는 recursive한 함수.
        if(p < r){
            int q = (p+r)/2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
    }

    public static void merge(int[] A, int p, int q, int r){ //원래 배열(A) 전체를 가져오고 p~q와 q+1~r까지의 배열을 병합한 후 원래 배열에 넣어주는 함수.

        int [] temp = new int [A.length];
        int i = p;
        int j = q+1;
        int k = p;

        while(i <= q && j <= r){ //두 배열의 처음부터 서로 비교한 후 더 작은 것을 임시 배열인 temp에 넣어주는 과정.
            if(A[i] < A[j]) temp[k++] = A[i++];
            else temp[k++] = A[j++];
        }
        while(i <= q) temp[k++] = A[i++]; //오른쪽에 있는 배열이 먼저 끝났을 시 왼쪽 배열에 남아있는 나머지를 temp에 넣어주는 과정.
        while(j <= r) temp[k++] = A[j++]; //왼쪽에 있는 배열이 먼저 끝났을 시 오른쪽 배열에 남아있는 나머지를 temp에 넣어주는 과정.
        for(int a=p; a<=r; a++) A[a] = temp[a]; //임시 배열에 정렬된 배열을 원래 배열 A에 넣어주는 괴정.(이때, A에 arr을 받아오므로 결국 arr배열에 정렬된다.)
    }
}

---

[시간 복잡도]

 

위와 같이 T(n)은 n/2와 n/2 총 n개의 element들을 비교하므로 n이 걸린다. 이를 2개의 element를 비교하는 T(2)까지 내려가보면 총 n/2개의 T(n) 즉, 2 * n/2 = n번의 비교가 생긴다. 이때 T(n) ~ T(2) 까지의 깊이는 logn이므로 시간복잡도는 O( n * logn )이다.

 

합병정렬의 경우, 정렬이 되어있는 정도에 따라 시간복잡도가 달라지지 않고 모두 O(nlogn)이다. 기본 정렬인 선택, 버블, 삽입 정렬들보다는 빠른 속도의 정렬인 것이다.