Merge Sort

merge sort(합병정렬) 은 크기가 N인 입력을 1/n 크기로 분할하고, 각각에 대해 재귀적으로 다시 합병정렬을 수행한 후,n개의 정렬된 부분은 합병하는 정렬 알고리즘이다.

대부분 n은 2로, 2-way 병합정렬을 수행한다.

합병정렬 알고리즘은 분할정복(divide & conquer) 알고리즘에 속한다.

분할정복알고리즘은 보통 주어진 집합의 데이터를 작은 부분집합들로 나누어서(divide) , 부분집합에서 문제를 해결하고 (conquer) , 부분집합들을 합쳐서 문제를 푸는 (combine) 3가지 단계로 이루어 진다. 보통 재귀적으로 푼다.

병합정렬의 경우 , combine하는 작업이 conquer 과정과 일치한다. 즉 combine하는 과정에서 배열을 정렬하며 문제를 해결한다.

파이썬으로 구현해본 mergeSort는 다음과 같다. 이미 정렬된 2개의 배열을 병합하는 과정은 필요가 없으므로 중간에 arr[mid] 값이 arr[mid+1]값보다 작은 경우에는 병합과정이 수행되지 않도록 구현되어 있다.

자바 버젼은 파이썬 버젼과 syntax외에는 흐름 자체는 큰 차이는 없으나, 정렬결과를 임시적으로 저장할 배열을 미리 초기화해두는 점만 유의하면 되겠다. (code참조)

Python Version.

def merge_sort(arr,lt,rt):
    # 하나의 부분집합은 이미 정렬된 부분집합으로 보고 반환한다.
    if(lt>=rt):
        return 
    #절반으로 부분집합을 나누어 각각에 대해 다시 재귀적으로 호출한다.
    mid = (lt+rt)//2;
    merge_sort(arr,lt,mid);
    merge_sort(arr,mid+1,rt);

    p1 = lt;
    p2 = mid+1;
    #combine 과정 (정렬된 두개의 리스트를 합친다)

    ## 최적화 : arr[mid] 값이 arr[mid+1] 보다 작다면 이미 정렬되어있다는 의미므로 굳이 아래의 정렬과정을 반복할필요가없다. 
    if(arr[mid] <= arr[mid+1]):
        return;

    tmp = [];
    while p1<=mid and p2<=rt:
        if(arr[p1] >= arr[p2]):
            tmp.append(arr[p2]);
            p2+=1;
        else:
            tmp.append(arr[p1]);
            p1+=1;
    if(p1<=mid):
        tmp += arr[p1:mid+1];
    else:
        tmp += arr[p2:rt+1];
    arr[lt:rt+1] = tmp;

if __name__=="__main__":
    arr = [1,4,7,24,6,8,21,12,63];
    print("before merge_sort : {}".format(arr));
    merge_sort(arr,0,len(arr)-1);
    print("after merge_sort : {}".format(arr));

Java version.

public class MergeSort {


        /***
         * @param arr = 정렬할 배열
         * @param lt = 분할 및 병합할 시작위치
         * @param rt =  분할 및 병합할 마지막위치
         * @param buff = 임시적으로 정렬된 결과를 담을 배열
         */
        public static void mergeSort(int[] arr,int lt, int rt,int[] buff){

            if(lt>=rt){
                return;
            }
            int mid = (lt+rt)/2;
            // 1. divide
            mergeSort(arr,lt,mid,buff);
            mergeSort(arr,mid+1,rt,buff);
            int index = lt;
            int p1 = lt;
            int p2 = mid+1;
            if(arr[mid] <= arr[mid+1]){
                return;
            }
            // 2. combine 
            /***
             * mid을 중심으로 2개의 정렬된 배열을 병합하는 과정 
             * p1(lt)가  p2(mid+1) 를 계속해서 비교해서 더 작은값을 임시배열에 삼입한다.
             * p2가 rt(병합할 배열의 마지막 위치)값을 넘은경우, p1에 남은 요소가 있으면 
             * 해당 값들을 임시배열에 삼입. 반대의 경우 (p1이 mid값을 넘은 경우)도 동일하게
             * p2에 남은 요소가 있다면 해당 값들을 임시배열에 삼입
             */
            while(p1<=mid || p2<=rt) {
                if( p2 > rt || (p1<=mid && arr[p1]<arr[p2] )){
                    buff[index++] = arr[p1++];
                }
                else{
                    buff[index++] = arr[p2++];
                }
             }
            for(int i = lt ; i <= rt ; i++){
                arr[i] = buff[i];
            }
        }
        public static void main(String[] args){
            int[] arr = {1,4,7,24,6,8,21,12,63};
            /*
                중간에 정렬결과를 저장할 buffer를 만든다. 
                method안에서 buffer를 만들게 되면 계속해서 메모리 공간이 잡힘으로, 
                정렬전에 미리 공간을 할당하고, 
                정렬후에는 GC 대상이 되도록 null값을 할당한다.
            */
            int[] buff = new int[arr.length];
            System.out.println("Arrays.toString(arr) = " + Arrays.toString(arr));
            mergeSort(arr,0,arr.length-1,buff);
            System.out.println("Arrays.toString(arr) = " + Arrays.toString(arr));
            buff = null;
        }
}

시간,공간복잡도

merge sort의 시간복잡도는 worst case에도 O(NlogN)의 시간복잡도를 가지며, 입력의 크기 만큼의 임시 버퍼를 만들어주어야 함으로, O(N)의 공간 복잡도를 가진다.