[Algorithm] Merge Sort | SUMFIのBlog

Merge Sort

합병정렬은 Divde and Conquer의 개념을 적용한 정렬이다
Stable한 정렬로 정렬하고자하는 엔티티 벡터를 절반씩 분할해가며 분할이 완료된 후 합병을 하는 과정에서 대소관계 비교를 통해 정렬을 수행한다
O(n logn)의 시간복잡도와 O(n)의 공간 복잡도를 가진다
Dive and Conquer의 개념을 이해하면 쉽게 구현이 가능하다

동작 원리

오름차순 정렬 기준

정렬하고자 하는 엔티티 벡터의 크기가 1보다 작아질 때 까지 재귀적으로 분할을 수행한다
정렬하고자 하는 엔티티 벡터의 크기가 1이라면 분할된 두 엔티티 벡터 배열끼리 대소관계 비교를 통해 병합을 수행한다
병합을 수행할 때 기존 엔티티 벡터에 대한 정보를 저장하기 위한 공간이 필요하다
병합이 완료되면 이전 주소로 돌아가 전체 엔티티 벡터의 병합이 완료될 때 까지 병합을 수행한다

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <random>
#include <numeric>

using namespace std;

inline void Merge(vector<int> &mergeSortVec, int left, int mid, int right){
    vector<int> sorted(right-left+1);
    int L = left, R = mid + 1, Index = 0;
    while(L<=mid && R<=right){
        if(mergeSortVec[L] < mergeSortVec[R])
            sorted[Index++] = mergeSortVec[L++];
        else
            sorted[Index++] = mergeSortVec[R++];
    }
    if(L<=mid){
        for(;L<=mid;){
            sorted[Index++] = mergeSortVec[L++];
        }
    }
    else{
        for(;R<=right;){
            sorted[Index++] = mergeSortVec[R++];
        }
    }
    for(Index = left; Index <= right; Index++)
        mergeSortVec[Index] = sorted[Index - left];
}

void MergeSort(vector<int> &mergeSortVec, int left, int right){
    if(left < right){
        int mid = (left + right) >> 1;
        MergeSort(mergeSortVec,left,mid);
        MergeSort(mergeSortVec,mid+1,right);
        Merge(mergeSortVec, left, mid, right);
    }
}

int main() {
    std::srand ( unsigned ( std::time(0) ) );
    vector<int> vec(1000);
    iota(begin(vec),end(vec),1);
    std::shuffle(std::begin(vec), std::end(vec), default_random_engine {});
    cout<<"Before Cell Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    cout<<endl;

    MergeSort(vec, 0, vec.size()-1);

    cout<<"After Cell Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    return 0;
}

Merge Sort

동작 원리

구현

같이보기