[호붕싸 모각코 12차] 합병정렬 (Merge Sort)

작성자	임혜진
소 감	머지소트는 분할 정복으로 착착 정렬되는 모습이 직관적이라 재미있다. 코드 구현도 어렵지 않다. 마지막 모각코라서 아쉬웠다. 지금까지 모각코를 수행하니 혼자 공부하는 것보다 더 많은 양을 공부할 수 있었고 글로 정리하며 서로 공유할 수 있어서 좋았다.
일 시	2025. 3. 10. (월) 18:00 ~ 21:00
장 소	미래관 429호 자율주행스튜디오
참가자 명단	신수민, 임혜진, 배세은, 김윤희 (총 4명)
사 진

 

---

 

 

📍 합병정렬 (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 알고리즘이 아니다.