오늘은 병합 정렬에 대하여 알아보고자 합니다.

개요

여라개의 정렬된 자료의 집합을 병합하며 한개의 정렬된 집합을 만드는 방식을 병합 정렬이라고 합니다.

전체 원소들에 대하여 정렬을 수행하는게 아니고, 부분적으로 집합을 분할하며 각 집합에 대해 정렬 작업을 완성하고 정렬된 집합들을 다시 병합하면서 하는 분할 정복(divde and conquer)기법을 사용합니다.

2개의 정렬된 자료의 집합을 결합하며 만드는 방식을 2-way 병합이라고 하며 n개의 정렬된 자료 집합을 하나의 집합으로 만드는 병합 방식을 n-way 병합이라고 합니다.

2-way

1. 입력 자료를 같은 크기의 부분 집합 2개로 분할합니다.

2. 집합의 원소들을 정렬합니다.

3. 집합의 크기가 충분히 작지 않으면 다시 재귀적으로 호출하여 다시 분할을 반복합니다.

4. 정렬된 집합들을 다시 하나의 집합으로 병합합니다.

알고리즘

mergeSort(arr[],m,n){
    if(arr[m:n].length()>1)then{
        arr.divide();
        mergeSort();
        mergeSort();
        merge(arr[m:middle],arr[middle+1:n]);
    }
}

크기가 n인 배열 arr의 원소를 병합 정렬하는 알고리즘 의사 코드입니다.

이는 배열을 반으로 나누어 부분 배열을 만들고, 각 부분의 배열에 대하여 다시 재귀적으로 호출하여 반복합니다. 분할이 끝나면 merge 연산을 합니다. merge 연산은 부분 배열을 정렬하면서 방합하는 작업을 반복하게 해줍니다.

병합 정렬은 n개의 원소에 대하여 2*n개의 메모리 공간을 사용하며, 시간 복잡도는 O(n log2 n)입니다.