Merge sort 병합 정렬

병합 정렬은 '분할 정복'의 아이디어로 구현된 정렬 방법이다. 

 

분할 정복 이란?

분할 : 문제를 단순하게 분할

정복 : 분할된 문제를 해결

결합 : 결과를 취합하여 마무리

3가지의 절차를 걸쳐 문제를 해결하는 것을 말한다.

 

따라서 병합 정렬은 가장 최소 단위까지 문제를 쪼개는 게 우선이며,

이 과정에서 재귀적인 함수 호출이 요구된다. 

 

만약 6개의 숫자가 무작위로 나열되어 있다면, 함수의 재귀적 호출을 통해

해당 배열의 개수의 / 2 개로 계속해서 쪼갠 뒤, 쪼개진 배열에 정렬을 수행해준다.

더 이상 쪼개질 수 없는 상태가 되었을 때, 함수를 종료하게 된다. 

#include <iostream>
#include <vector>

using namespace std;

void MergeResult(vector<int>&, int, int, int);

void MergeSort(vector<int>& v, int left, int right)
{
    //더 이상 쪼갤 수 없을 때 종료
    if(left >= right) 
        return;
        
    int mid = (left + right) / 2;
    
    //mid를 기준으로 왼쪽
    MergeSort(v, left, mid);
    //mid를 기준으로 오른쪽
    MergeSort(v, mid+1, right);
    
    //정복 및 결합
    MergeResult(v, left, mid ,right);
}

void MergeResult(vector<int>& v, int left, int mid, int left)
{
    vector<int> temp; //정렬된 배열을 임시 저장
    
    int leftIndex = left;
    int rightIndex = mid + 1;
    
    while(leftIndex <= mid && rightIndex <= right)
    {
        if(v[leftIndex] <= v[rightIndex])
        {
            temp.push_back(v[leftIndex]);
            leftIndex++;
        }
        else
        {
            temp.push_back(v[rightIndex]);
            rightIndex++;
        }
    }
    
    //leftIndex가 먼저 mid에 도달한 경우
    if(leftIndex > mid)
    {
        while(rightIndex <= right)
        {
        	//쪼개진 배열들은 이미 나열된 상태이기 때문에 배열에 넣어주는 것만으로 해결.
        	temp.push_back(v[rightIndex]);
            rightIndex++;
        }
    }
    else //rightIndex가 먼저 right에 도달한 경우
    {
        while(leftIndex <= mid)
        {
            temp.push_back(v[leftIndex]);
            leftIndex++;
        }
    }
    
    //임시 배열을 다시 v에 복사
    for(int i=0;i<temp.size();i++)
    	v[left+i] = temp[i];
}