병합정렬(Merge Sort)

컴퓨터 공학 스터디 W1.자료구조와 알고리즘, 언어론👏

병합정렬이란?

많은 정렬들 중 하나인 병합정렬은 무엇일까? 병합정렬은 비교 기반 알고리즘으로 전체 원소를 하나의 단위로 분할한 후에 분할한 원소를 다시 병합하는정렬 방식을 말한다. 병합정렬은 합병정렬, 머지정렬이라 부르기도 한다.

병합정렬의 단계

병합정렬의 단계를 '분할, 정복, 결합' 3가지로 나누어 볼 수 있다.
분할 단계에서는 입력된 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복 단계에서는 부분 배열을 정렬한다. 여기서 부분 배열의 크기가 충분히 작지 않다면 순환 호출을 이용하여 다시 분할 정복법을 적용해준다. 결합 단계에서는 정렬된 부분 배열을 하나의 배열로 결합한다.

예시

간단한 예시를 보면서 병합정렬을 소개해보겠다. 사과를 재배하는 과수원 8곳이 있다. 각 과수원의 사과나무의 수는 다음과 같다고 한다.

이 과수원들을 사과나무가 적은 순서대로 배열을 하려고 한다. 병합정렬을 진행하기 위해서는 저 배열되어 있는 사과나무들을 가장 작은 단위로 분할해주어야 한다. 그렇게 된다면

저렇게 하나의 과수원씩 나누어지게 된다. 이제 첫번째 정렬을 진행해보겠다. 가장 작은 단위가 되기 전 단계인 두개의 과수원끼리 정렬을 해준다. 그렇게 되면 저렇게 두개에 과수원끼리 먼저 비교를 해준다. 그렇게 정렬을 진행하면 첫번째 정렬의 결과는 다음과 같다.

이제 두번째 정렬을 진행해야한다. 두번째 정렬은 4개의 과수원끼리 진행시켜준다. 먼저 사과나무 5개가 있는 과수원과 사과나무 1개가 있는 과수원을 비교해서 정렬해준다. 그럼 사과나무 1개인 과수원이 가장 앞으로 오게 된다. 그 다음으로는 사과나무가 5개인 과수원과 사과나무가 3개인 과수원을 비교해준다. 사과나무 1그루인 과수원 다음으로는 사과나무 3개인 과수원이 오게되고, 그 다음으로는 5개, 6개인 과수원이 차례대로 오게된다. 그 다음 4개의 과수원도 동일하게 진행해주면 두번째 정렬의 결과는 다음과 같게된다.

이제 마지막으로 8개의 과수원을 모두 비교해주어야한다. 아까 두번째 정렬을 했을때와 동일한 방식으로 정렬을 진행해준다. 나무가 1개인 과수원과 2개인 과수원을 먼저 비교하고 정렬하고, 3개인 과수원과 2개인 과수원을 비교해서 정렬하는 형식으로 계속 정렬을 진행한다. 그렇게 되면 최종 정렬의 결과는 다음과 같다.

병합정렬 장단점

병합정렬은 정렬시 추가적인 공간을 사용함으로써 같은 값을 가지는 원소의 상대적인 순서를 유지하는 안정정렬이라는 장점이 있다. 하지만 만약 레코드를 배열로 구성하면 임시 배열이 필요하고 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다. 그러나 만약 레코드를 연결 리스트로 구성하여 합병 정렬할 경우 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을만큼 작아진다. 크기가 큰 레코드를 정렬할 경우에 연결리스트를 사용한다면 병합정렬은 모든 정렬 중 가장 효율적일 수 있다.

병합정렬의 사용

병합정렬은 Linked List의 정렬이 필요할 때 유용하게 사용된다고 한다. LinkedList 는 삽입 및 삭제 연산에 있어, 유용하지만 접근 연산에 있어서는 유용하지 않다고 한다. 배열의 경우에는 인덱스를 통해 접근하기 때문에 시간복잡도가 O(1)이지만, LinkedList는 Head 부터 탐색해야 하기 때문에 시간 복잡도가 O(n)이다. 그래서 임의적인 접근에서는 오버헤드가 증가하게된다. 이러한 이유로 Linked List는 순차적인 접근과 같은 병합정렬을 사용하는 것이 유용하다.

병합정렬의 시간복잡도

분할과정 : 단순 분할만 진행하기 때문에 비교, 이동이 수행되지 않는다
순환호출 : 절반씩 나누어 호출되기 때문에 log n이다
이동 : 임시 배열에 복사했다가 다시 원 배열에 가져와야한다 -> 배열의 요소가 n개일 경우 이동은 2n번 발생한다
시간복잡도 = O(n log n)

병합정렬 구현 코드

#include <stdio.h>

int temp_arr[8];

void merge(int *arr, int start, int middle, int end){
    int i = start;
    int j = middle + 1;
    int k = start;
    
    while(i<=middle && j<=end){
        if(arr[i]<=arr[j]) temp_arr[k] = arr[i++];
        else temp_arr[k] = arr[j++];
        k++;
    }
    
    if(i>middle){
        for(int t=j;t<=end;++t){
            temp_arr[k] = arr[t];
            ++k;
        }
    }
    else{
        for(int t=i;t<=middle;++t){
            temp_arr[k] = arr[t];
            ++k;
        }
    }
    
    for(int t=start;t<=end;++t){
        arr[t] = temp_arr[t];
    }
}


void mergeSort(int *arr, int start, int end){
    if(start < end){
        int middle = (start + end) / 2;
        mergeSort(arr, start, middle);
        mergeSort(arr, middle+1, end);
        merge(arr, start, middle, end);
    }
}
int main(){
    
    int i;
    int arr[8] = {6, 5, 3, 1, 8, 7, 2, 4};
    
    mergeSort(arr, 0, 7);

    for(i=0;i<8;++i){
        printf("%d ", arr[i]);
    }
    
    return 0;
}

병합정렬을 C언어로 구현한 코드이다. 코드에 대한 설명을 하자면 먼저 merge 함수를 보면 while문은 데이터를 비교하여 정렬 및 삽입을 해주는 코드이고 if문에서 남은 데이터를 삽입해준다. for문에서는 임시저장용 배열에 저장된 값을 원래 배열에 넣어준다. mergeSort 함수에서는 merge 함수를 이용하여 크기가 1일때까지 호출하고 1단위까지 쪼갠 후 병합한다. 메인 함수에서는 배열의 결과를 출력한다.