[Algorithm] Merge sort / 병합 정렬

1. Merge sort

• 분할 정복기법을 활용하여 정렬시키는 정렬 알고리즘이다. 재귀를 활용하여 큰 문제를 작은 문제로 쪼개서 풀이한 다음 return하면서 값을 합쳐서 도출해낸다.
• 정렬 로직 수행 간 초기 정렬상태를 보장하는 안정 정렬 방식이다
• 시간복잡도 : O(NlogN) // 공간복잡도 : O(N)

Merge sort의 로직 동작 과정

1. 정렬할 배열의 처음과 끝 인덱스를 함수의 인자로 넘겨준다. 

2. 처음과 끝 인덱스를 2로 나눈, 즉 mid = (left + right)/2. mid를 기준으로 재귀함수를 호출하여 범위가 1이 될 때 까지 나눠준다.

3. 정렬한 후 값을 복사해서 return 한다.

mid를 기준으로 나눴을 때 왼쪽 부분의 범위 : left~mid

mid를 기준으로 나눴을 때 오른쪽 부분의 범위 : mid+1~right

배열을 정렬하는 범위 : left~right

3-1. 배열의 왼쪽 오른쪽 값을 비교해서 sorted 배열에 담는다.이 과정을 거치면 무조건 오른쪽 또는 왼쪽 배열 중 먼저 정렬이 완료되는 배열이 존재한다.

3-2. 만약 3-1에서 왼쪽 배열이 먼저 정렬됐다면 남은 배열인덱스에 오른쪽 배열을 넣어주고, 반대로 오른쪽 배열이 먼저 정렬됐다면 남은 배열 인덱스에 나머지 왼쪽 배열을 넣어준다.  >>  return으로 항상 정렬된 배열이 올라오기 때문에 남은 배열을 for문을 통해 그대로 남은 인덱스에 넣어줘도 된다.

4. 정렬한 배열의 값을 입력받은 원래 배열에 복사해준다.

Merge sort 장/단점

장점

 - 퀵 정렬은 데이터의 정렬 상태에 따라 최악의 경우 O(N^2)의 시간 복잡도를 가지지만 merge sort는 항상 절반으로 분할하기 때문에 수행시간이 초기 데이터의 상태에 구애받지 않는다.

- 안정 정렬 방식이기 떄문에 초기 데이터의 정렬 상태를 보장할 수 있다.

단점

 - 초기 주어진 데이터를 정렬해서 저장해 놓을 수 있는 임시 저장 공간이 필요하다. 그래서 공간복잡도는 O(N)이 나온다. 

 - 데이터의 크기가 큰 경우 이동 횟수가 많아진다.

2. Code

#include <bits/stdc++.h>

using namespace std;

vector<int> arr;
int* sorted;

void Print() {
    for (int i = 0; i < arr.size(); i++) {
        cout << sorted[i] << ' ';
    }
    cout << "\n";
}

void merge(int left, int mid, int right) {
    int leftIdx = left;   //mid를 기준으로 나눴을 때 왼쪽 부분의 인덱스
    int rightIdx = mid+1; // mid를 기준으로 나눳을 때 오른쪽 부분의 인덱스
    int sortIdx = left;   // 정렬해야하는 배열 위치

    //나눈 배열중에서 둘중에 왼쪽에 있는 애들이 먼저 정렬되거나 또는
    //오른쪽에 있는 애들이 먼저 정렬되면 그만돌기
    while(leftIdx <= mid && rightIdx <= right) {
        if(arr[leftIdx] <= arr[rightIdx]) {
            sorted[sortIdx] = arr[leftIdx];
            leftIdx++;
        }
        else {
            sorted[sortIdx] = arr[rightIdx];
            rightIdx++;
        }
        sortIdx++;
    }

    //이전 while문에서 왼쪽애들이 먼저 정렬됐다면 나머지 남은 오른쪽애들을 남은 인덱스에 넣어주기
    if(leftIdx > mid) {
        for(int i = rightIdx; i <= right; i++) {
            sorted[sortIdx] = arr[i];
            sortIdx++;
        }
    }
    else { //위의 반대
        for(int i = leftIdx; i <= mid; i++) {
            sorted[sortIdx] = arr[i];
            sortIdx++;
        }
    }
    
    //정렬된 배열 복사
    for(int i = left; i <= right; i++) {
        arr[i] = sorted[i];
    }
} 

void division(int left, int right) {
    if(left >= right) return;
    
    int mid = (left + right) / 2;

    division(left, mid);
    division(mid+1, right);
    merge(left, mid, right);

}

void mergeSort() {
    division(0, arr.size()-1);
}


int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        arr.push_back(rand() % 100);
    }

    sorted = new int[n];

    clock_t start, finish;
    double duration;
    start = clock();

    mergeSort();

    finish = clock();
    Print();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "Merge sort로 " << n << " 개 원소 정렬에 걸린 시간 " << duration << "초" << "\n";
}