병합 정렬

분할 정복이라는 개념이 들어간다.

 

• 분할 문제를 더 단순하게 분할
• 정복 분할된 문제 해결
• 결합 결과 취합 마무리

3 단계로 이루어짐 만약 8개의 원소가 있다면 반으로 나눠서 각각 정렬한다.

분할을 최대한 많이 함 그 다음 정렬된 각각의 문제들을 결합하여 다시 정렬.

당연히 재귀적인 방식을 이용한다.

시간 복잡도 : MergeResult 함수는 N 근데 MergeResult 를 반반씩 쪼개 질 때마다 사용하므로 logN 만큼 사용한다 즉, O(NlogN)이다.

 

void MergeResult(vector<int>& v, int left, int mid, int right)
{
    int leftI = left;
    int rightI = mid + 1;
    vector<int> temp;

    while (leftI <= mid && rightI <= right)
    {
        if (v[leftI] < v[rightI])
        {
            temp.push_back(v[leftI]);
            leftI++;
        }
        else
        {
            temp.push_back(v[rightI]);
            rightI++;
        }

       
    }
   
    // 왼쪽이 정렬이 먼저 됨
    if (leftI > mid)
    {
        while (rightI <= right)
        {
            temp.push_back(v[rightI]);
            rightI++;
        }
    }
    // 오른쪽이 정렬이 먼저 됨
    else
    {
        while (leftI <= mid)
        {
            temp.push_back(v[leftI]);
            leftI++;
        }
    }
    // v 를 인자로 넘길 때 left, right 즉 범위를 알려주었기 때문에 left 부터 시작해서 넣어주면
    // 자연스럽게 right 범위까지 정렬되어 채워질것이다.
    for (int i = 0; i < temp.size(); ++i)
    {
        v[left + i] = temp[i];
    }
}

void MergeSort(vector<int>& v, int left, int right)
{
    if (left >= right)
        return;


    int mid = (left + right) / 2;
    MergeSort(v, left, mid);
    MergeSort(v, mid + 1, right);

    MergeResult(v, left, mid, right);
}