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

📍 합병정렬 (Merge Sort)

합병 정렬은 Divide & Conquer (분할정복) 방식을 기반으로 한 정렬이다. 배열을 쪼개고 쪼갠 뒤 합치는(merge) 과정에서 정렬이 된다. 그래서 Merge Sort이다.

 

📍 C++ 구현 코드

class Solution {
public:
    void merge(vector<int>& nums, int start, int mid, int end){
        int n = nums.size();
        vector<int> tmp(n+1);
        for(int i=0;i<n;i++){
            tmp[i] = nums[i];
        }
        int i = start;
        int k = start;
        int j = mid+1;
        while(i<=mid && j<=end){
            if(tmp[i]<tmp[j]){
                nums[k++] = tmp[i++];
            }else{
                nums[k++] = tmp[j++];
            }
        }
        
        while(i<=mid){
            nums[k++] = tmp[i++];
        }
        while(j<=end){
            nums[k++] = tmp[j++];
        }

    }

    void mergesort(vector<int>& nums, int start, int end){
        if(start<end){
            int mid = (start+end)/2;
            mergesort(nums,start,mid);
            mergesort(nums,mid+1,end);
            merge(nums,start,mid,end);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        mergesort(nums,0,nums.size()-1);
        return nums;
    }
};

https://leetcode.com/problems/sort-an-array/ 에서 위의 코드를 실행시킬 수 있습니다. (testcase는 통과하지만 시간초과 발생)

 

📍 코드 동작 원리

분할 정복 방식이다보니 함수를 나누어 작성하여 코드가 길어졌다. mergesort()는 주어진 길이를 반으로 나누고, merge()를 호출한다. merge()에서는 두 배열을 앞에서부터 하나씩 비교해가며 더 작은 수부터 차곡차곡 채운다. 이때 tmp라는 변수명을 가진 임시 배열을 만들어서 nums를 복사해둔 후 사용한다. 비교해가며 작은 수부터 채우는 과정이 merge()함수의 마지막 while문 3개인데 이 부분의 구현이 재미있다. while문을 통해서 i 와 j 인덱스가 하나라도 끝까지 도달하면 while문을 빠져나가고 남은 배열만 쭉 채워넣는다.

 

📍 시간복잡도(time complexity)

 

Merge Sort는 재귀 호출 부분이 두 번 있는 binary recursion 알고리즘이다. O(nlogn)만에 구현 가능하다!

 

📍 Stable / NOT In-Place

 

Merge sort는 stable한 알고리즘이다. 반으로 나누고, 또 그 과정에서 차곡차곡 합쳐지니 배열 내 같은 숫자인 원소의 순서가 흐트러질 일이 없다. 하지만 MergeSort의 치명적인 단점은 바로 In-Place 알고리즘이 아니라는 것이다. 위의 코드에서 merge () 함수가 사용될 때 tmp라는 임시 배열을 사용했다. 이는 input 길이만큼의 메모리를 추가로 필요로 한다는 것이므로 Merge Sort는 In-Place 알고리즘이 아니다.

 

---

끝.

머지소트는 분할 정복으로 착착 정렬되는 모습이 직관적이라 재미있다. 코드 구현도 어렵지 않다.