[알고리즘] Java로 구현하는 쉬운 Merge Sort (병합 정렬, 합병 정렬)

알고리즘을 시작할 때 가장 먼저 배워야 할 것은 정렬, 즉 sorting이라고 생각한다.

버블 정렬, 선택 정렬, 퀵 정렬 등 많은 정렬이 있지만, 내가 사용하는 것은 병합 정렬이다. 

 

병합 정렬(=합병 정렬)의 시간복잡도는 O(nlogn)인데, 왜 이 시간 복잡도가 나오는지 먼저 알아보자.

 

병합 정렬은, 원소가 저장되어 있는 배열을 계속 쪼개서 길이가 1인 배열을 만들고, 그 이후 정렬하면서 합치는 알고리즘이다.

merge sort의 진행 과정 (출처 : 위키피디아 https://en.wikipedia.org/wiki/Merge_sort)

Merge sort 는 binary tree 형태로 쪼개기 때문에 가질 수 있는 최대 깊이는 log n 이 된다. 이때, 각 분할 (n개) 별로 합병을 진행하므로, 총 시간 복잡도는 O(nlogn)이 된다.

 

이때, quick sort는 최악의 경우 O(n^2)의 시간 복잡도를 가지게 되는데, merge sort는 항상 O(nlogn)의 시간 복잡도를 가지고 있으니, merge sort를 사용하는 것이 좋다.

 

Java로 merge sort를 구현해볼 건데, merge sort의 진행과정을 코드를 통해 천천히 알아보자.

전체 코드는 다음과 같다.

실행결과
1 9 8 5 4 2 3 7 6 
1 2 3 4 5 6 7 8 9 

굉장히 간단하게 구현이 가능한데, 첫줄부터 찬찬히 살펴보도록 하겠다.

    public static void mergeSort(int start, int end) {
        if (start<end) {
            int mid = (start+end) / 2;
            mergeSort(start, mid);
            mergeSort(mid+1, end);

            int p = start;
            int q = mid + 1;
            int idx = p;

            while (p<=mid || q<=end) {
				// 안정 정렬이기 때문에 index를 유지
                if (q>end || (p<=mid && src[p]<=src[q])) {
                    tmp[idx++] = src[p++];
                } else {
                    tmp[idx++] = src[q++];
                }
            }

            for (int i=start;i<=end;i++) {
                src[i]=tmp[i];
            }
        }
    }

먼저, merge sort라는 함수의 formal parameter인 int start와 int end를 보자.

start는 merge sort를 진행할 배열의 시작 인덱스를 의미하고, end는 마지막으로 포함될 배열의 인덱스를 의미한다.

앞서 올린 그림처럼 binary tree 형태로 쪼개기 때문에 int mid라는 start와 end의 중간 지점을 저장한다.

 

그 이후, 실제 분할을 진행하는데 첫 분할은 시작점부터 중간점까지인 mergeSort(start, mid)가 되고, 두 번째 분할은 중간점 다음부터 끝점까지인 mergeSort(mid+1, end)가 된다.

 

그다음, int p와 int q에 두 분할의 첫 번째 원소의 인덱스를 저장한다.

이 값을 저장하는 이유는, 해당 인덱스의 값을 비교하여 어떤 원소를 참조할지 정하기 때문이다.

start는 항상 mid+1보다 작기 때문에, 분할의 저장 위치는 start 지점이 된다. 그래서 int idx는 p가 된다.

 

그리고, p가 mid이하거나 q가 end이하일 때 동작해야 한다. 미만이 아닌 이유는 원소의 개수가 1개일 때까지 쪼개기 때문이다. 그리고 동시에 종료가 되지 않을 수 있으니 두 경우를 &&으로 하지 않고 ||으로 하는 것에 주의하자.

 

첫 번째 분할에서 원소를 가져오는 경우는 다음과 같다.

1. 두 번째 분할의 원소를 이미 다 가져온 경우 (q> end)

2. 첫 번째 분할에서 가져오지 않은 원소가 있고, 첫번째 분할의 첫 원소 값이 두 번째 분할의 첫 원소 값보다 작은 경우

 

위 조건을 표현하면 다음과 같다.

1. q> end

2. p <=mid && src [p]<src [q]

 

두 조건 중 하나 이상 만족하면 첫 번째 분할에서 원소를 가져오므로 두 조건 사이에 or을 사용한다.

그래서 if 문이 if (q>end || (p <=mid && src [p]<src [q])) 이렇게 선언된 것이다.

 

if 문에 결과에 따라 1번 분할의 첫 번째 값이나, 2번 분할의 첫번째 값을 정렬된 값을 임시 저장하는 배열인 tmp의 idx에 저장해준다.

이때, 가져온 원소의 다음 인덱스를 다시 비교하기 위해 p++ 또는 q++를 조건에 맞게 해 준다.

( idx도 당연히 ++ 해줘야 한다. 그다음 최솟값을 찾아서 저장할 거니까 )

 

그리고, 1번 분할과 2번 분할의 모든 원소를 가져오면, start 부터 end까지 정렬된 값을 다시 src라는 원래 배열에 저장해준다.

 

이렇게 merge sort가 동작하고, 이번엔 main 함수를 살펴보자.

 

    public static int[] src;
    public static int[] tmp;
    public static void main(String[] args) {
        src = new int[]{1, 9, 8, 5, 4, 2, 3, 7, 6};
        tmp = new int[src.length];
        printArray(src);
        mergeSort(0, src.length-1);
        printArray(src);
    }

 

src는 내가 정렬해야 할 원소가 담겨있는 배열이고, tmp는 src와 똑같은 길이를 가진 배열로, 정렬된 원소를 임시 저장한다. (물론 이렇게 하지 않고, src의 원소를 그대로 두고 tmp에 새로 정렬된 값을 저장한 후 리턴해도 된다.)

 

내가 구현한 merge sort는 end 지점의 원소까지 검사하기 때문에 mergeSort(0, src.length-1) 임에 주의하자.

만약 mergeSort(0, src.length)로 실행한다면 ArrayBoundOutOfRange 에러가 발생할 것이다.

 

 

설명이 잘 되었는지 모르겠으나, 코드가 워낙 간단하니 코드를 천천히 리뷰해보고, 원리를 이해하여 언제든지 필요할 때 쉽게 사용할 수 있었으면 좋겠다!

 

이모저모 쓸모가 많은 알고리즘이다.

 

혹 이해가 안 되는 부분이 있거나, 수정하면 더 좋을 것 같은 부분이 있다면 언제든지 알려주면 좋겠다!