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

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

 

 

병합정렬이란

병합 정렬(Merge Sort)는 분할 정복 알고리즘의 일종으로,  배열을 반으로 나누어 각각을 정렬한 후, 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열을 만드는 방식입니다.

병합정렬의 과정, 출처: 위키백과

 

이 정렬 방법은 다음과 같은 순서로 진행됩니다.

1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다. 부분 배열의 크기가 1 또는 0이 될 때까지 이 과정을 반복합니다.

2. 정복(Conquer): 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 사용해 다시 분할 단계로 돌아갑니다.

3. 결합(Merge): 정렬된 부분 배열들을 하나의 배열로 병합합니다. 이 과정에서 최종적으로 정렬된 배열이 생성됩니다.

병합 정렬의 시간 복잡도는 모든 경우에 대해 O(n log n)을 보장합니다. 이는 분할 단계에서의 log n과 병합 단계에서의 n이 곱해지는 형태로 나타납니다. 그러나 병합 정렬은 추가적인 메모리 공간을 필요로 하는 단점이 있습니다. 이는 병합 과정에서 새로운 배열을 생성하기 때문입니다.

병합 정렬은 데이터의 크기가 크거나, 데이터가 디스크에 저장되어 있어 메모리 내에서 정렬이 불가능한 경우에 유용합니다. 이는 병합 정렬이 데이터를 순차적으로 처리하기 때문에, 디스크에서의 입출력 횟수를 최소화할 수 있기 때문입니다.

 

병합정렬 코드

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l+(r-l)/2;

        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

 

테스트 코드

int main() {
    int arr[] = {20, 30,10,21,5,39,2};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    cout << "Given array is \n";
    for (int i=0; i < arr_size; i++)
        cout << arr[i] << " ";

    mergeSort(arr, 0, arr_size - 1);

    cout << "\nSorted array is \n";
    for (int i=0; i < arr_size; i++)
        cout << arr[i] << " ";

    return 0;
}

 

테스트 결과

Given array is
20 30 10 21 5 39 2
Sorted array is
2 5 10 20 21 30 39