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

합병 정렬(Merge Sort)이란?

 비교기반 정렬 알고리즘이다.

일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 

임시 배열 공간을 활용하여 정렬을 수행한다.

장점

• 안정적인 정렬 방법이다.
• 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)

단점

• 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

 

합병 정렬 과정

   1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
   2. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
   3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
   4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.  

---

합병 정렬 그림

알고리즘 구현

임시 배열을 사용하는 방식

추가 메모리를 사용하여 정렬을 수행한다.

/**임시 배열을 활용한 합병 정렬*/

int* sorted; //임시 배열

void merge(vector<int>& list, int start,int mid, int end){
    int i = start;
    int j = mid + 1;
    int k = start;
    int l;

    //병합
    while(i <=mid && j <= end){
        if(list[i] <= list[j]){
            sorted[k++] = list[i++];
        }else{
            sorted[k++] = list[j++];
        }
    }

    //남아 있는 값 복사
    if(i>mid){
        for(l = j; l<=end; l++){
            sorted[k++] = list[l];
        }
    }else{
        for(l = i; l<=mid; l++){
            sorted[k++] = list[l];
        }
    }

    //임시 배열에서 리스트로 이동
    for(l = start; l<=end; l++){
        list[l] = sorted[l];
    }
}

void mergeSort(vector<int>& list, int start, int end){
    if(start < end){
        int mid = (start + end) / 2;

        mergeSort(list, start,   mid); //왼쪽 절반 분할 정복
        mergeSort(list, mid + 1, end); //우측 절반 분할 정복
        merge(list, start, mid, end ); //합병
    }
}

int main(){
    vector<int> list = {1,29,58,32,2,7,8,100};
    sorted = new int[list.size()];
    
    mergeSort(list,0,list.size() -1);
    
    delete sorted;
    
    return 0;
}

 

연결 리스트(Linked List)를 사용하는 방식

연결 리스트를 사용하게 되면 주소만 가리키게 되기 때문에 메모리 오버플로우가 나지 않는다.

/**Linked List를 활용한 병합 정렬*/

struct Node{
    int value;
    Node* next = NULL;
};

//리스트를 두개로 분할하는 함수
void splitLeftRight(Node* ref, Node** left, Node** right){
    Node* slow = ref;
    Node* fast = ref->next;

    while(fast != NULL){
        fast = fast->next;

        if(fast != NULL){
            slow = slow->next;
            fast = fast->next;
        }
    }

    *left = ref;
    *right = slow->next; //mid + 1 과 동일
    slow->next = NULL; // NULL로 잡아줘야 두개로 나뉘게 된다.
}

//합병을 진행하는 함수
Node* merge(Node* left, Node* right){
    Node* merged = NULL;

    if(left  == NULL) return right;
    if(right == NULL) return left;

    if(left->value <= right->value){
        merged = left;
        merged->next = merge(left->next,right);
    }else{
        merged = right;
        merged->next = merge(left,right->next);
    }

    return merged;
}

void mergeSort(Node** ref){
    Node* head = *ref;
    Node* left;
    Node* right;

    if(head == NULL || head->next ==NULL){
        return;
    }

    //분할
    splitLeftRight(head, &left, &right);
    
    //왼측 분할
    mergeSort(&left);
    
    //우측 분할
    mergeSort(&right);

    //왼측, 우측 합병
    *ref = merge(left,right);
}

void addValue(Node** head, int value){
    Node* newNode = new Node();

    newNode->value = value;

    //헤드의 주소에 해당 하는 것을 next로 설정
    newNode->next = *head;

    //헤드를 새로운 노드의 주소로 변경
    *head = newNode;
}

int main(){
    vector<int> list = {27, 10, 12, 20, 25, 13, 15, 22};

    Node* linkedList = new Node();

    for(int i =0; i< list.size(); i++){
        addValue(&linkedList,list[i]);
    }

    mergeSort(&linkedList);
    
    return 0;
}

시간 복잡도

• 완전히 분할하는데 log(n) 레벨을 생성한다.
• 합병하는데 할당된 리스트의 길이 만큼, 즉 N번 반복한다.
• 평균 시간복잡도는 O(n * log2 n)

 

---